2

I was wondering if someone could look over this problem set and tell me if my answers are wrong and if so how. Thanks in advance

Let V = {S,A,B,a,b} and T = {a,b}. Find the language generated by the grammar (V,T,S,P) when the set of productions consists of:

  1. S $\rightarrow$ AB, A $\rightarrow$ ab, B $\rightarrow$ bb

    • My answer: {abbb}
  2. S$\rightarrow$ AB, S $\rightarrow$ aA, A $\rightarrow$ a, B $\rightarrow$ ba

    • My answer: {aba,aa}
  3. S $\rightarrow$ AB, S $\rightarrow$ AA, A $\rightarrow$ aB, A $\rightarrow$ ab, B $\rightarrow$ b

    • My answer: {abb, abab}
  4. S $\rightarrow$ AA, S $\rightarrow$ B, A $\rightarrow$ aaA, A $\rightarrow$ aa, B $\rightarrow$ bB, B $\rightarrow$ b

    • My answer: {$a^{4n}$ $b^{n+m}$ | n,m $\geq$ 0}
  5. S $\rightarrow$ AB, A $\rightarrow$ aAB, B $\rightarrow$ bBa, A $\rightarrow$ $\lambda$, B $\rightarrow$ $\lambda$

    • My answer: {$a^n$ $b^{n+m}$ $a^m$ | n,m $\geq$ 0}

1 Answers1

1

The first three are fine.

In the fourth one, the first production applied gives you either $AA$ or $B$. If it’s $B$, all you can generate is $\{b^n:n\ge 1\}$. If it’s $AA$, each of the $A$s can generate $\{a^{2n}:n\ge 1\}$, i.e., any positive even number of $a$s, so $AA$ can generate $\{a^{2n}:n\ge 2\}=\{a^n:n\ge 4\text{ and }n\text{ is even}\}$. Putting everything together, we see that the language is

$$\{a^{2n}:n\ge 2\}\cup\{b^n:n\ge 1\}\;.$$

In the fifth one you must start a derivation by getting $AB$. Now let’s see what $B$ can generate: from a $B$ all you can do is apply $B\to bBa$ some number $n\ge 0$ of times and then apply $B\to\lambda$, getting $b^na^n$. Thus, $B$ produces the words $b^na^n$ with $n\ge 0$. Similarly, $A$ produces $a^mB^m$ if we apply $A\to aAB$ some number $m\ge 0$ of times and then apply $A\to\lambda$. Each of those $m$ $B$s can produce any $b^na^n$ with $n\ge 0$. Thus, for each $m\ge 0$ and $n,n_1,\ldots,n_m\ge 0$ the grammar can produce the word

$$\underbrace{a^mb^{n_1}a^{n_1}b^{n_2}a^{n_2}\ldots b^{n_m}a^{n_m}}_{\text{from }A}\underbrace{b^na^n}_{\text{from }B}\;.$$

Any of the integers $n_k$ or $n$ can be $0$. It’s clear that the language includes $\{b^na^n:n\ge 0\}$, since we get these when we apply $A\to\lambda$ to the first $A$ generated. Now suppose that we apply $A\to aAB$ some number $m\ge 1$ times. Then we can get any word of the form

$$a^mb^{n_1}a^{n_1}\ldots b^{n_r}a^{n_r}$$

such that $0\le r\le m+1$ and $n_1,\ldots,n_r\ge 1$ (if $r>0$). The words $b^na^n$ satisfy this description for $m=0$, so the language is

$$\{a^mb^{n_1}a^{n_1}\ldots b^{n_r}a^{n_r}:m\ge 0\text{ and }0\le r\le m+1\text{ and }n_1,\ldots,n_r\ge 1\}\;.$$

The first block of $a$s tells you the maximum number of blocks of the form $b^na^n$ that can follow it, and the rest of the word must consist of blocks of that form.

Brian M. Scott
  • 616,228