After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me.

Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the right-linear grammar $G= (\{S,A\},\{0,1\},S,P)$, where $P$ consists of the following rules:

$S\rightarrow 1A|01S|\lambda$

$A\rightarrow 00A|11S$

Prove that $L(G)\subseteq L(r)$ and vice versa.

In general, how exactly do I prove that a regular grammar describes the same language as a regular expression?

  • $\begingroup$ Your title doesn't match your body. $\endgroup$ Apr 21 at 5:25

Let's try to simplify your grammar. First, notice that $A$ generates $(00)^*11S$, and so we can get rid of $A$, obtaining $$ S \to 1(00)^*11S \mid 01S \mid \lambda $$ Similar reasoning shows that your grammar generates the language $$ (1(00)^*11+01)^* = ((1(00)^*1+0)1)^*, $$ which is identical to your regular expression.

While the reasoning above is informal, it can be made formal with some work.

  • $\begingroup$ Thank you prof for your answer. However I have a few doubts, Firstly, I have been trying to prove double inclusion for some time now. I have been trying to do this using induction on the length of the derivation of a word w. Is there a way I could proceed through that? $\endgroup$ Apr 21 at 5:33
  • $\begingroup$ Proving all of this formally requires some work, but the reason that your statement is correct is what I wrote. $\endgroup$ Apr 21 at 5:37
  • $\begingroup$ could you pls give me a hint as to what this work is. As in, just the way I should proceed. $\endgroup$ Apr 21 at 5:48
  • $\begingroup$ Show that every word in the language of the regular expression can be generated by the grammar. This can be done directly. Then show that every word generated by the grammar belongs to the language of the regular expression. This can be done by describing all words generated by the two nonterminals, by induction on the length of the word (or of the production). $\endgroup$ Apr 21 at 5:50

In general, a proof will depend on what you're allowed to assume.

There are well-known procedures for

  1. Converting any right-regular grammar into a NFA
  2. Converting any NFA into a DFA
  3. Minimizing any DFA

Steps 2 and 3 can be performed directly on (strictly) right-regular grammars as well.

Two regular languages are equal if and only if their minimal DFAs are isomorphic (including placement of their initial and final states).

If you can't assume the correctness of these procedures, you'll basically have to present them and prove them correct on the fly.


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.