Proving that a language defined by a regular expression is equivalent to a right linear grammar

Question

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?

Answer 1

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.

Answer 2

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.