Give CFG and PDA for the words that start and end with the same symbol

Problem Detail: 

I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite know how to accomplish it.

The best I can figure is that I need to use non-determinism, but I don't quite know how to apply it in this circumstance.

Here's the CFG that I came up with:

\begin{align*} A &\to 1B1 \mid 0B0 \mid \epsilon\\ B &\to 1B \mid 0B\mid \epsilon \end{align*}

The PDA, insofar as I managed to come up with:

The notation here, just in case it's not universal: $a,b \to c$ means "When you see symbol $a$, pop symbol $b$ off the stack and push symbol $c$ onto the stack."

Any pointers on how to accomplish this?

Asked By : agent154

Answered By : vonbrand

A DFA is simple: From start state $A$ on 0 go to $B$, from $B$ with 0 go to $C$ (final), from $B$ with 1 stay in $B$, from $C$ with 0 stay in $C$, from $C$ with 1 go to $B$. Use a mirror for 1.

The PDA is just the DFA which essentially ignores the stack (rewrite the stack start symbol with itself on each move).

A CFG is just: $$ \begin{align*} S &\rightarrow 0 A 0 \mid 1 A 1 \mid 0 \mid 1 \\ A &\rightarrow 0 A \mid 1 A \mid \epsilon \end{align*} $$ A CFG more in line with the DFA is: $$ \begin{align*} S &\rightarrow 0 A \mid 1 B \mid 0 \mid 1 \\ A &\rightarrow 0 A \mid 1 A \mid 0 \\ B &\rightarrow 0 B \mid 1 B \mid 1 \end{align*} $$

Best Answer from StackOverflow

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