Specify the Grammar for the Non-regular Language

172 Views Asked by At

I am trying to find the Grammar for the Non-regular (I've proven it by Pumping Lemma) Language:

$$ L=\left\{0^{k+1}1^k0^k~~|~~ k\ge1 \right\}$$

It should generate the following:

$0010, 0001100,0000111000,0000011110000,\ldots$

I have tried several rules but with no success.

1

There are 1 best solutions below

2
On BEST ANSWER

$L$ isn’t context-free. Apply the pumping lemma for context-free languages. Assume that $L$ is context-free, let $p$ be the pumping length, and start with the word $s=0^{p+1}1^p0^p\in L$. Then there is a decomposition $s=uvwxy$ such that $|vwx|\le p$, $|vx|\ge 1$, and $uv^kwx^ky\in L$ for each $k\ge 0$.

Since $|vwx|\le p$, either $vwx$ is a substring of $0^{p+1}1^p$, or it’s a substring of $1^p0^p$. In either case pumping $v$ and $x$ affects at most two of the three blocks $0^{p+1}$, $1^p$, and $0^p$, so the resulting word cannot belong to $L$.

Added: Now that the grammar is not required to be context-free, there are many possibilities; here is one that is fairly easy to understand, if not very efficient.

$$\begin{align*} S&\to 0010\mid AXZ\\ X&\to AAXB\mid AAYB\\ YB&\to L0\\ 0L&\to L0\\ IL&\to LI\\ AL&\to IR\\ RI&\to IR\\ R0&\to 0R\\ RB&\to L0\\ RZ&\to M0\\ 0M&\to M0\\ IM&\to N1\\ IN&\to NI\\ AN&\to 0S\\ S0&\to 0S\\ SI&\to IS\\ IS1&\to N11\\ 0S1&\to 0T11\\ 0T&\to T0\\ AT&\to 00 \end{align*}$$

The $S$ and $X$ productions build a string of the form $A^{2n+1}YB^nZ$; the idea is that $A^{2n+1}Y$ will eventually become $0^{n+2}1^{n+1}$, and $B^nZ$ will become $0^{n+1}$. Here $n$ is the number of times an $X$ production is applied, so $n\ge 1$.

The $YB$ production then turns the leftmost $B$ to a $0$ and becomes $L$. $L$ moves to the left until it encounters an $A$; it turns the $A$ into an $I$ and becomes $R$. (Each $I$ will eventually become a $1$.) The $R$ moves back to the right until it encounters a $B$ or the final $Z$. If it encounters a $B$, it turns the $B$ into a $0$ and becomes an $L$. The $L$ moves left, turns the first $A$ that it encounters into an $I$, and becomes an $R$, which moves to the right until it either encounters a $B$, in which case the cycle repeats, or encounters the final $Z$. At that point we have $A^{n+1}I^n0^nRZ$, and after applying the $RZ$ production we have $A^{n+1}I^n0^nM0$.

The $M$ moves left until it encounters an $I$. It turns the $I$ into a $1$, moving past the $1$ and becoming $N$; at this point we have $A^{n+1}I^{n-1}N10^{n+1}$. The $N$ moves left until it encounters an $A$, turns the $A$ into a $0$, and becomes $S$, which moves back to the right until it encounters a $1$. If there is an $I$ immediately to its left, it turns that $I$ into a $1$ and moves left past it as $N$ again. This process repeats until the last $I$ has been changed to $1$, at which point we have $A0^nS1^n0^{n+1}$. The $S$ then drops off one more $1$ and becomes $T$, which moves left until it encounters the last remaining $A$, and the $AT$ collapse into $00$, leaving $0^{n+1}1^{n+1}0^{n+1}$ for some $n\ge 1$. The case $n=0$ is covered by the production $S\to 0010$.