Context free grammar issue at pda

Question

I'm studying for my computing languages and I have some problem on getting the production rules from a push down automata.

The automaton accepts all strings over alphabet $\{e,k,q,y\}$ of the form $w\,kyyk\,w'$ such that $|w|=|w'|$.

There are the productions rules I get.

S -> QkyykK
Q -> qQ
Q -> yQ
Q -> eQ
Q -> kQ
Q -> epsilon

K -> Kq
K -> Ky
K -> Ke
K -> Kk
K -> epsilon

I don't understand how to have the same number on the left and on the right. Hope anyone can help me or explain me cause I am having so problems with that exercice. I use jflap for testing if it's accepted or rejected.

Answer 1

You enforce the property of having an equal number of characters to the left and the right by only having rules that add an equal number of characters.

At the moment, your approach is essentially, "Start with $kyyk$ and add stuff to the left and the right." In this case, "stuff" is the non-terminal symbols $K$ and $Q$, each of which can expand to any string in $\Sigma^*$. Whenever you're expanding two non-terminals in a context-free language, they're expanded completely independently, so there's no way to control their interaction, e.g., to require that both strings have the same length. This means that the approach of generating the left-stuff and right-stuff from two non-terminal symbols can't work.

Instead, you need to take the opposite approach. Start with nothing and simultaneously expand the stuff on the left and right.

Answer 2

As David correctly noted, you work from the outside in, adding a single character to the left and the right sides. Here's a simpler example: suppose you want all strings over $\{a,b\}$ of the form $wabw'$ where $|w|=|w'|$. This grammar will do what you want: $$\begin{align} (1)\quad S&\rightarrow aSa\\ (2)\quad S&\rightarrow aSb\\ (3)\quad S&\rightarrow bSa\\ (4)\quad S&\rightarrow bSb\\ (5)\quad S&\rightarrow ab\\ \end{align}$$ Every one of the first four productions will generate strings of the form $xSy$ where $x$ and $y$ are single characters, and production (5) will eventually replace the variable $S$ with the "central" string $ab$. For example, to generate the string $bab\ ab\ aaa$ we could do this derivation: $$ S\stackrel{(3)}{\Longrightarrow}bSa\stackrel{(1)}{\Longrightarrow}baSaa\stackrel{(3)}{\Longrightarrow}babSaaa\stackrel{(5)}{\Longrightarrow}\underbrace{bab}_wab\underbrace{aaa}_{w'} $$ It's clear that in each of the steps in the derivation $w$ and $w'$ will always have the same length and can consist of any strings over the alphabet, which is exactly what you need. In your example, with a four-character alphabet, you'll need 17 productions: 16 for all possible combinations of the four characters on the left and right sides, plus one more to get the $kyyk$ in the middle.