1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – vonbrand Sep 10 '15 at 19:24
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So your $ \mathbb{N} = \{0, 1, 2, \dotsc\}$, while mine is $ \mathbb{N} = \{1, 2, 3, \dotsc\}$ $\endgroup$ – vonbrand Sep 10 '15 at 19:25
  • 1
    $\begingroup$ Yes, I assume that $0$ is a natural number. $\endgroup$ – Dominik Sep 10 '15 at 19:26
0
$\begingroup$

Am I approaching this problem in the correct way?

Yes.

$\endgroup$

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.