[Solved]: Build a regular grammar for a regular language

Problem Detail: 

The language considered is the infinite set of all chains that meet the following conditions.

Conditions:

1) They consist of symbols from the set {1,a,b}.  2) They always start with the subchain '1a'. 3) They always include at least one subchain 'aa'. 

For example:

1aa, 1abaa, 1aaab, 1aab1a, ... etc. 

One regular expression for this language seems to be like this: $1a ((1+b)^* a)^* (a (1+b)^* )^* a (1+b+a)^*$

How to find a regular grammar for this language?

I've thought of many ways but it seems to be too complex for me. I tried the following as solution, but it is not correct, I guess.

G ({1,a,b}, {A,S}, P, S) P: S -> 1S|bS|aA A -> 1A|bA|1a 

Asked By : Happy Torturer

Answered By : babou

This language was already considered by the same OP in another question Build a regular expression to define a regular language. But then, posters are told not to ask two questions in the same post.

I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $1a(1+a+b)^*$, and by conditions 1 and 3, $(1+a+b)^*aa(1+a+b)^*$.

You take the FA for them, both having 3 states (4 if you count a dead state), and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton (6 states if you count a dead state).

From that FA you can get a regular expression for the language, which is $1(a+a(1+a+b)^*a)a(1+a+b)^*$.

But you can also get a regular grammar:

$S \rightarrow 1T$
$T \rightarrow aX \mid aY$
$X \rightarrow 1X \mid aX \mid bX \mid aY$
$Y \rightarrow a \mid aZ$
$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$

which derives directly from the automaton.

In more details: Why do it as I did above?

Proving that a regular expression defines the language specified by a set of such conditions can be long and tedious. The same is true for a grammar or an automaton. This is why the proper way of answering such a question is to find a systematic way of building the desired result from elementary components for which things are obvious to prove.

Here, as I had already answered, elementary components are the regular languages defined respectively

• by conditions 1 and 2: $1a(1+a+b)^∗$ ;

• by conditions 1 and 3: $(1+a+b)^∗aa(1+a+b)^∗$ .

For each of these 2 languages, it is easy to find the regular expression (above) or to give a regular grammar or a finite-state automaton (FA). Each has a 3 states FA that recognizes it (4 states including a dead state).

To get a FA for the language meeting all three conditions, you only have to get the intersection of these two languages. There is a standard cross-product construction for building a FA recognizing the intersection of two regular languages. This construction is easy to apply by hand in our example. It produce a 5 states FA for the language defined by all three conditions (or a 6 states FA, including a dead state).

From this last FA, it is easy to build either the regular expression or the regular grammar given above.

Since the answer was built in a systematic way using well known techniques (that have been proved correct long ago), there is no need to prove that the resulting regular expression, grammar or FA are correct. Barring of course mistakes in the use of the constructions ... but then, you can also make mistakes in proofs.

I added the precision about dead states so that no one gets confused. But, except for some constructions, it is often simpler just to omit dead states and transitions leading to them.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24751