Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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}\}$
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.
