Context free grammar for these langauges?

110 Views Asked by At

I've been working on trying to generate context free grammars for different problems and currently I'm working on these but after trying over and over, I can't come up with ones for these:

1) the palindrome langauge $\{z \in \{0,1\}^* \mid z = z^R\}$ where $R$ is the reverse of $z$.

2) $\{0^x1^y0^z \mid x,y,z \in \mathbb{N} \text{ and } (x=y \text{ or } y=z)\}$

1

There are 1 best solutions below

0
On

HINT: Palindromes are easy: build them from the middle out. You can get all of them of even length with the productions $S\to\lambda\mid 0S0\mid 1S1$; you’ll have to work just a little harder to get the ones of odd length. (I use $\lambda$ for the empty word; many people use $\varepsilon$.)

Your second language is the union of two simpler languages:

$$L_1=\{0^x1^x0^y:x,y\in\Bbb N\}$$

and

$$L_2=\{0^x1^y0^y:x,y\in\Bbb N\}\;.$$

For $L_1$ you can start with $S\to AB$, then add productions so that $A$ produces strings of the form $0^x1^x$, and $B$ produces strings of zeroes. (The trick of building from the middle out will help you again here.) $L_2$ has a very similar grammar, and combining the grammars is straightforward: if their initial symbols are $S_1$ and $S_2$, start with $S\to S_1\mid S_2$.