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

Question

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?

Answer 1

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*} $$

Answer 2

Your grammar is wrong: you don't generate $0$ and $1$ which are certainly in the language, and you generate $\varepsilon$ which may or may not be in it, depending on the exact formulation. Both are easy to fix and the rest looks fine to me. Can you prove correctness?

In order to get a PDA, there are multiple strategies.

1. Use the canonical construction from your grammar.
2. Construct a PDA (with smarts).
3. Note that the only thing you need to remember is the first symbols. Thus, finite memory is sufficient; the language is regular. See vonbrand's answer.

When you construct automata, note the following rules of thumb:

• You need a starting state.
• If your language is not empty, you need (reachable) accepting states.
• If your language is not finite, you need loops.

Your automaton already fails on these counts. Instead of succumbing to the formal model, try this: write a regular program that accepts the language, with the following restrictions:

• You can only use one while loop, no recursion.
• You have one stack (with push, pop, isempty?, nothing else)¹.
• You have one pointer in the input string, and it can only move to the right.
• You can only have a fixed (i.e. independent of the input) number of boolean auxiliary variables.

If you have this, rewrite the program in automaton form; the main task will be to figure out the states from the possible values of your variables.

Be aware that this strategy only works to obtain deterministic automata. Non-deterministic ones are often smaller/simpler, or even necessary (e.g. for inherently ambiguous context-free languages), so you have to become comfortable in the model at some point. This is merely a stepping stone.

---

1. If you disallow the stack, too, the same works for DFA.