1
$\begingroup$

Let $G = (\{A,S\}, \{a,b\}, S, P\}$ be the grammar with the following productions: \begin{align} & S \to aAb | Sb \\ & A \to aAb | ab \end{align}

  1. What is the language $L(G)$ generated by the grammar?
  2. Prove your answer to 1. by induction.

Here is my attempt. I think that the language generated by $G$ is $$L= \{a^nb^{n+k} \mid n\geq2,k\geq0. \} $$ I need to prove that $L = L(G)$ by induction on length, but I don't know how to do it properly because I have two parameters ($n,k$). There also need to be two directions to the proof.

I found this post, but it is of no help to me.

What is the base case? I tried looking about distinguishing whether the length is even or odd, and I think I got the pattern between $(n,k)$ correctly, but I really don't have a clue how to start the proof.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Start by showing that $L(A)$ (the language generated by the grammar if the starting symbol is $A$) is $L_A = \{ a^n b^n \mid n \geq 1 \}$. You prove this by double inclusion:

  • In order to prove that $L_A \subseteq L(A)$, prove by induction on $n$ that $A \Rightarrow^* a^nb^n$.
  • In order to prove that $L(A) \subseteq L_A$, prove by induction on the length of the derivation that if $A \Rightarrow^* \alpha$ then either $\alpha = a^n b^n$ for some $n \ge 1$, or $\alpha = a^n A b^n$ for some $n \geq 0$. (In fact we won't need this direction, but it's good practice.)

Now we can show that $L = L(G)$, again by double inclusion:

  • In order to prove that $L \subseteq L(A)$, prove by induction on $k$ that $S \Rightarrow^* aAb^{k+1}$.
  • In order to prove that $L(A) \subseteq L$, prove by induction on the length of the derivation that if $S \Rightarrow^* \alpha$ then either $\alpha = S b^k$ for some $k \geq 0$, or $\alpha = a^{n+1}Ab^{n+k+1}$ for some $n,k \geq 0$, or $\alpha = a^{n+2} b^{n+k+2}$ for some $n,k \geq 0$.
$\endgroup$
1
  • $\begingroup$ thank you so much! $\endgroup$
    – Maya Cohen
    May 2 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.