# Different context-free grammars for the same language

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

• Checking whether two context-free grammars generate the same language is undecidable. Jul 23 '18 at 13:59

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.