Are these two context free grammars equivalent?

154 Views Asked by At

Let $\Sigma = \{a,b\}$. A CFG for the language $\{a^nb^m~|~n > 2m\}$ can be written as: $$ \begin{align} S &\to aaSb\\ S &\to A\\ A &\to aA\\ A &\to a \end{align} $$

Would it be equivalent to write this CFG as the following? $$ \begin{align} S\to aaSb~|~aS~|~a \end{align} $$

Thanks

1

There are 1 best solutions below

0
On

Yes. They will be the same.

S-->aaSb,S-->A, A-->aA, A-->a

and

S--> S-->aaSb | aS | a

generate the same grammar, .$a^{2n+k}b^n, n \ge 1, k \ge 1$