0
$\begingroup$

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: enter image description here

  • 0
    Yes, you can; it’s basically the same idea, but easier, because there’s less to keep track of.2012-11-10

2 Answers 2

1

If this is a specific question, for two explicitly given grammars, we wait for your answer.

If it is an "abstract" question, how do I prove that two right-linear grammars generate the same language, you probably want to transfer them into finite automata (which is easy). For these you can test equality, because the language of such an automaton can be tested for emptiness, after performing suitable boolean operations. That will involve complement, for which it is better to turn them into deterministic automata.

(edit) thanks for the grammars. In fact the question is the other way around: given automata (as in the table) transform them into grammars (which you did) and for those show they are equivalent. Your observation is basically OK. Note however that $B$ and $D$ are not exactly the same, but the operation you suggest will indeed work.

Formally I would argue like this. For every derivation in grammar for L1 I can easily find a derivation in L2 with the same result (in $B$ and $C$ on letter $1$ move to $D$ etc). The reverse is as you said. For every derivation for L2 I will get one for L1 by changing $D$ into $B$. As the derivations determine the language you have a proper argument.

  • 0
    I posted the question. and yes, it means final states.2012-11-10
0

To show this we can convert both grammars to DFA's and then we should minimize these two DFA's . If we get the same DFA it means that these two grammars are equivalent (since we know that minimum DFA is unique)