World's most popular travel blog for travel bloggers.

[Solved]: help with the probability of acceptance of a Nondeterministic Pushdown automata

, , No Comments
Problem Detail: 

I have this nondeterministic pda: $$\Sigma= \{a,b,c\}$$

and

$$ L=\{\omega\ \epsilon\ \Sigma^*\ |\ \omega\ = \alpha\beta\beta^R\gamma\ and\ \alpha,\beta,\gamma\ \epsilon\ \Sigma^*\ and\ |\beta|\ >3 \} $$

So once i have create the NPDA, i have to calculate the probability of accepting a correct word, i know it depends on the size of $\alpha$ and the "free" jumps ($\varepsilon,\varepsilon->\varepsilon$). My problem is that i can't find the exact function of probability can someone explain me how to do it?

Thanks.

Asked By : Curious Bystander

Answered By : Hendrik Jan

In general when constructed in a natural way, you have to guess the correct position of $\beta$, so you have to have two positions right.

But there is a catch. In fact $L$ can alternatively be defined as $\{\omega \mid \omega = \alpha\beta\beta^R\gamma \text{ and } |\beta|=4 \}$. This is seen as folows: if you find any substring $\beta\beta^R$ then the central part of length 4+4=8 will also satisfy the palindromic substring constraint. So, $L$ is regular, and one can find a DFA for it.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18464

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback