0
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ Checking whether two context-free grammars generate the same language is undecidable. $\endgroup$ – Yuval Filmus Jul 23 '18 at 13:59
2
$\begingroup$

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.

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