Are these two grammars equivalent?

Question

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?

You are certainly right, $\Lambda$ is in the language generated by the first grammar, not the second. Be careful with terminology, a grammar doesn't "print out" anything. Moreover, $\Lambda$ is nothing, what would it mean to "print it out"? — vonbrand, Sep 10 '15 at 19:24

score 1 · Answer 1 · answered Sep 10 '15 at 19:24

1

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}\}$.

answered Sep 10 '15 at 19:24

Dominik

19,963

So your $ \mathbb{N} = {0, 1, 2, \dotsc}$, while mine is $ \mathbb{N} = {1, 2, 3, \dotsc}$ – vonbrand Sep 10 '15 at 19:25
1

Yes, I assume that $0$ is a natural number. – Dominik Sep 10 '15 at 19:26

score 0 · Answer 2 · answered Sep 10 '15 at 19:23

0

Am I approaching this problem in the correct way?

Yes.

answered Sep 10 '15 at 19:23

Thumbnail

563

Are these two grammars equivalent?

2 Answers2