I have two right linear grammars and I need to prove they both generate the same language.
What is the right way to do it?
L1:
$S \rightarrow 0A$
$S \rightarrow 1B$
$A \rightarrow 0A$
$A \rightarrow 1B$
$A \rightarrow \varepsilon$
$B \rightarrow 0C$
$B \rightarrow 1B$
$C \rightarrow 0B$
$C \rightarrow 1B$
$C \rightarrow \varepsilon$
L2:
$S \rightarrow 0A$
$S \rightarrow 1B$
$A \rightarrow 0A$
$A \rightarrow 1B$
$A \rightarrow \varepsilon$
$B \rightarrow 0C$
$B \rightarrow 1D$
$C \rightarrow 0B$
$C \rightarrow 1D$
$C \rightarrow \varepsilon$
$D \rightarrow 0C$
$D \rightarrow 1D$
I know that we can clearly see it from the grammars. Since in L2, D and B are the same, we can replace D with B and get equivalent grammar. But what is the correct way to prove it?
================================================================ Here is the question: