I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it.

Show language $L$ is context free, where $L = \{\text{all strings where middle two symbols are the same}\}$


1 Answer 1


For this problem, it's easier to come up with a CFG than it is to invent a PDA. First, notice that the strings should all be of even length, otherwise it's not clear what "middle two symbols" should mean. Here are some hints to get you going.

Hint 1. Could you have grammar rules $T\rightarrow (something)$ which would generate all strings $xx$, where $x$ is a symbol from your alphabet?

Hint 2. If you had a start variable $S$, could you make productions of the form $S\rightarrow (symbol_1)\; S\; (symbol_2)$ that would generate all sentential forms $\alpha\;S\;\beta$ where $\alpha$ and $\beta$ can be any strings over your alphabet and have the same length?

If you can do these two tasks, the CFG is easy.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.