Converting CFG to PDA

Question

I have the following CFG,

$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$

This is the CFG for the following language:

$$L= \left\{w \text{#} x\mid w^R \text{ is a substring of }\ x \text{, where } x,w\in \{a, b\}^*\right \}$$

I have a problem with constructing PDA for this CFG.

My attempt

My idea was to store characters in stack until "#" character, then as soon as the sequence of reversed characters go, pop from the stack. If at the end of input stack is empty, then we are done.

The problem is that for the following string, for example:

abbaa#aabbbbbbb(aabba)bbbbbb

when we read characters after "#", PDA will pop 4 characters, the it will see that the sequence is not valid and proceed with input. How can I return these 4 characters back so that I can check sequence again because I need full stack to proceed with accepted reversed substring that I have showed in brackets?

Answer 1

There is a general method to convert any CFG into a PDA. That's what jmite meant. You can find more details on that in wikipedia, or by searching this site.

But once you realized the language is $L=\{w\#x \mid w^R \text{ is a substring of }x\}$, you can forget about the grammar and directly construct a PDA.

The PDA works like what you describe in your question - it begins by putting $w$ into the stack. Then it needs to pop it out and compare it to $x$. But it might be that the substring $w^R$ is not a prefix of $x$, which causes your confusion.

The idea you are missing is the power of non-determinism: allowing the PDA to "magically" select the right way out of many possible ways to proceed.

In more details, the PDA will do the following. It will read some letters from the $x$ part of the input and just ignore them. Then, at some point which will be chosen "non-deterministically" (or, "magically", if you prefer), it will start comparing the input to the stack (and accept if there is a match; reject otherwise).

If indeed $w^R$ is a substring of $x$, there is a way for the PDA to make the right choice and start comparing the input to the stack exactly at the right position. This is enough to show that the PDA accepts (at least) $L$.

The concept of non-determinism is very strange, but think about it that way: the construction above defines infinitely many possibly (deterministic) PDAs: each one starts to pop the stack at a different time. "Accepting" a word in a non-deterministic way is defined as the event that at least one of the above machines accepts. The case of "Rejecting" a word is defined to be the event in which all the above machines reject.

Answer 2

You follow an algorithm similar to a "shift-reduce" parser. You only need one state. From this state, you can read the empty symbol and pop symbol X off the stack and replace it with the right side of any of its productions. Alternately, if the top of the stack is a terminal, and that terminal is next on the input tape, you read the letter and pop the letter. You start with S on the stack and you finish when the stack is empty.

If $\epsilon$ is the empty symbol, and $Z_0$ is the stack bottom, your automataon's transitions then are:

$\epsilon, Z_0/SZ_0$

$(\epsilon, X/\alpha )$ for each production $X \rightarrow \alpha $ in the grammar

$(a, a/\epsilon )$ for each terminal $a$

There is one state, each transition loops from this state to itself. You halt when you've read all symbols and the stack is empty.