Construct a grammar for $L=\{a^k b^l \ldots a^k b^l : k\geq 2 , l\geq 1\text{ and }a^k b^l \text{ is repeated at least once}\}$

62 Views Asked by At

$$L=\{a^k b^l \ldots a^k b^l : k\geq 2 , l\geq 1\text{ and }a^k b^l \text{ is repeated at least once}\}$$

As i can not work with LaTex I can not give the proper notation so if anyone could help with that too I'd apreaciate it.

To make things clear $L=\{aab,aabaab, \ldots\}$ but it can't be $\epsilon$.

1

There are 1 best solutions below

3
On BEST ANSWER

I’ll get you started.

Every word begins with at least two $a$s; these are followed by a string of zero or more $a$s, and those will be followed by one or more $b$s. Let’s not worry about any more than that for now. In addition to the initial non-terminal $S$ we’ll try to get away with two more non-terminals, one generating the $a$s after the first two and one generating the $b$s. A little experimentation leads to the following productions:

$$\begin{align*} &S\to aA\\ &A\to aA\mid aB\\ &B\to bB\mid b \end{align*}\tag{1}$$

Let’s check. Every derivation will begin by applying the production $S\to aA$. What can $A$ generate? If we apply the production $A\to aA$ $k$ times, we get $a^kA$. Eventually, though, we’ll have to apply $A\to aB$ to get rid of the $A$. At that point we have the following partial derivation:

$$S\Rightarrow aA\Rightarrow^k aa^kA\Rightarrow aa^kaB=a^{k+2}B$$

for some $k\ge 0$, so in this way we get all words of the form $a^kB$ with $k\ge 2$.

Now the only possible productions are $B\to bB$ and $B\to b$. We can apply the first of these $\ell$ times for any $\ell\ge 0$, but eventually we’ll have to apply the second in order to get rid of the $B$. We end up with the derivation

$$S\Rightarrow aA\Rightarrow^k aa^kA\Rightarrow a^{k+2}B\Rightarrow^\ell a^{k+2}b^\ell B\Rightarrow a^{k+2}b^{\ell+1}$$

for some $k,\ell\ge 0$. Thus, the productions $(1)$ generate precisely the words of the form $a^kb^\ell$ for $k\ge 2$ and $\ell\ge 1$.

Now see if you can adapt this to generate strings consisting of any positive number of words of this form. There’s more than one way to do it; I’ve added one in the spoiler-protected block below, but do try to find one on your own before looking at it.

Every derivation using $(1)$ ends by applying the production $B\to b$. If you add a production $B\to bS$, you have a choice of stopping with $B\to b$ or continuing the derivation by building another $a^kb^\ell$ block after the current one.