Given a finite state automaton with states Q (of which S is the start state and F is the set of final states), alphabet T and transition function t we would like to construct an equivalent regular grammar. Recall that to define a grammar we need to specify the set of terminals, the set of non-terminals, the start symbol and the set of production rules.
Note that all the productions introduced conform to the restrictions placed on regular grammar productions.
Consider the finite state automaton M=< {S,A,B,C}, {a,b,c}, t, S, {S,C} > where t is the following set:
t | = | { | (S,a)A, | |
(S,b)B, | ||||
(A,a)B, | ||||
(A,a)C, | ||||
(B,b)A, | ||||
(B,b)C, | ||||
(C,c)C | } |
Graphically, this automaton would appear as follows:
We will now construct an equivalent regular grammar. From steps 1, 2 and 3, we conclude that the terminal alphabet of the grammar is {a,b,c} and the non-terminal alphabet is {S,A,B,C}. The start symbol is the initial state S.
From every transition rule (q,a)q' we will now generate the production qaq':
S | aA | bB, | |
A | aB | aC, | |
B | bA | bC, | |
C | cC |
For every production (q,a)q' where state q' is a final state in F, we will generate the production rule qa. We have only three such transitions: (A,a)C, (B,b)C and (C,c)C which will generate the following productions:
A | a, | |
B | b, | |
C | c |
Finally, since S is a terminal state, we also add the production S. The resultant set of production rules is thus:
S | aA | bB | , | |
A | aB | aC | a, | |
B | bA | bC | b, | |
C | cC | c |
Note that S does not appear anywhere on the right hand side of rules thus making the regular grammar -free.
Give regular grammars equivalent to the following finite state automata: