Are these two grammars equivalent?

219 Views Asked by At

Let's say I have the following two grammars, and V is the start symbol.

$V \to aVb | ab | \Lambda$

and

$V \to aTb | ab$

$T \to aTb | \Lambda$

I refute that these are equivalent because with the first grammar we are able to print out an empty string, but are not possible to do this with the second grammar. Am I approaching this problem in the correct way?

2

There are 2 best solutions below

0
On

Am I approaching this problem in the correct way?

Yes.

2
On

That is correct. More specifically, the language that is generated by the first grammar is $\{a^n b^n \mid n \in \mathbb{N}\}$, while the second grammar generates $\{a^{n+ 1} b^{n + 1} \mid n\in \mathbb{N}\}$.