World's most popular travel blog for travel bloggers.

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

, ,
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.

#### 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.

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

3.2K people like this