Skip to main content
1 of 2
tylerh111
  • 392
  • 1
  • 7

Consider the following grammar $G$.

S -> aaaRbb
R -> aRb | aaRb | eps

We must prove that $L(G) = L$.

Proof: The variable $S$ in the grammar starts off with the smallest string in $L$. This string is $aaabb$ with $j=2$ and $i=3$ (since $0 < j = 2 < i = 3 < 2j = 4$).

The repetition happens within the variable $R$. Consider the string $s = a^ib^j \in L$. We want to see whether the string $s' = a^{i+1}b^{j+1}$ is in $L$. The first three conditions are trivial ($0 < j+1 < i+1$). The last condition is quick to check: \begin{align} i+1 &< 2(j+1) \\ i+1 &< 2j+2 \\ i &< 2j+1 \\ \end{align} So $s' \in L$. We can show $s' = a^{i+2}b^{j+1} \in L$ similarly.

Strings of the form $s' = a^{i+3}b^{j+1} \not \in L$ when $i+3 \geq 2(j+1)$. Suppose $s = aaabb$, then $s' = aaaaaabbb \not \in L$ as $\#_a(s') = 2\#_b(s')$. Thus we cannot add the rule R -> aaaRb.

Strings of the form $s' = a^{i+1}b^{j} \not \in L$ when $i+1 = 2j$. Suppose $s = aaabb$, then $s' = aaaabb \not \in L$ as $\#_a(s') = 2\#_b(s')$. Thus we cannot add the rule R -> aR.

Strings of the form $s' = a^{i}b^{j+1} \not \in L$ when $j+1 = i$. Suppose $s = aaabb$, then $s' = aaabbb \not \in L$ as $\#_a(s') = \#_b(s')$. Thus we cannot add the rule R -> Rb.

Thus, our grammar $G$ is complete. Hence $L(G) = L$.

tylerh111
  • 392
  • 1
  • 7