In context-free grammar, are both the following grammars correct for the same language?

$$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$

(grammar one)

$S \to S_1 | S_2$

$S_1 \to A_1B_1$

$A_1 \to aA_1 | a$

$B_1 \to aB_1b | \epsilon$

$S_2 \to A_2B_2$

$A_2 \to aA_2b | \epsilon$

$B_2 \to bB_2 | b$

(grammar two)

$S \to S_1 | S_2$

$S_1 \to \epsilon | aA_1$

$A_1 \to aA_1 | aB_1$

$B_1 \to aB_1b | a$

$S_2 \to \epsilon | A_2b$

$A_2 \to A_2b | B_2b$

$B_2 \to aB_2b | b$

Is there a rule I could use to check whether the grammar is correct for the given language (other than trying all the strings that come to my mind)?

  • 2
    $\begingroup$ Checking whether two context-free grammars generate the same language is undecidable. $\endgroup$ Jul 23, 2018 at 13:59

1 Answer 1


Grammar 1 matches a. Grammar 2 does not. So they are not identical, and at least one of them is not a grammar of your indicated language.

As Yuval Filmus indicates in a comment, the general question of whether two CFGs produce the same language is undecidable. Obviously, it can be decided in certain cases (such as this one); searching for a counterexample is usually straightforward, although it obviously won't terminate if the two grammars turn out to produce the same language.

For simple exercises like this one, you should be able to prove (or disprove) that a grammar produces a given language. A simple technique which often works is induction over the length of the string.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.