Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What are the grammars? –  Brian M. Scott Nov 10 '12 at 22:41
    
@BrianM.Scott here are the grammars. –  Mike Nov 10 '12 at 22:56
    
Have you learned yet about reducing a FSA to a minimal FSA? –  Brian M. Scott Nov 10 '12 at 23:14
    
@BrianM.Scott, yes, but these are finite state accepters. Can I reduce it the same way? since it doesn't have output. –  Mike Nov 10 '12 at 23:16
    
Yes, you can; it’s basically the same idea, but easier, because there’s less to keep track of. –  Brian M. Scott Nov 10 '12 at 23:18

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
This is what I assumed I should do. show that they have the same f.a. –  Mike Nov 10 '12 at 22:58
    
OK, I now see you have given the grammars. I would nevertheless draw them as automata to see what is happening. The $\epsilon$ productions correspond to final states. –  Hendrik Jan Nov 10 '12 at 22:58
    
I posted the question. and yes, it means final states. –  Mike Nov 10 '12 at 23:03

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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