Convert a Grammar into a transition Diagram - Convert Regular Expression into NFA

Convert a Grammar into Transition Diagram
The regular grammars are the only type of grammars that can be converted into transition diagram. We take an example to explain this conversion.
Example: convert the following grammar into transition diagram:
G=({S, R, U},{a, b, c}, P, {S}) where P is given by
S a?bU?cR
R abaU?U
U b?cS
The productions R abaU?U are not validate for regular grammar, so that we convert it into the following productions
R aX ?b?cS
X bY
Y aU
So that grammar has the following productions:
S a?bU?cR
R aX ?b?cS
X bY
Y aU
U b?cS
Therefore the transitions diagram for the grammar is shown in fig (11)

















The transition diagram may help the designer to build a lexical analyzer directly without using other steps. We use functions and procedures that read a character and check it according to some label.









Example: If we have the following grammar for recognizing a real number
<Real number>::= <integer> <fraction>
<integer>::= <digit>?<integer> <digit>
<fraction>::= <digit>?<fraction> <digit>
<digit>::= 0?1?2?…?9
We use the following steps:-
1- Construct a separate transition diagram for every grammar.

<Real number>:




< integer>:




<fraction>:



<digit>:





2- Substitute every non terminal with its transition diagram
1. Substitute the non terminal <integer> in transition diagram 1 with the transition diagram 2





2. Substitute the non terminal <fraction> in transition diagram that result from step-a with transition diagram-3.






3. Substitute the non terminal<digit> with transition diagram -4











Convert a Regular Expression into an NFA
We can generate an NFA from Regular expressions according to the following steps:-
1- Divide a regular expression R into its primitive components as follows:-
a- If there is ? in regular expression, we must build a start state (i) and a final state (f), and put ? as a label of the edge.


b- If there exist a terminal Symbol a in ?, we construct the NFA:-



c- If the regular expression R contains the expression P?Q we build a start and a final state, and we decomposed P and Q into Sp and Fp for P and SQ and FQ for Q.










d- If the regular expression R contains the expression P.Q, then the transition diagram that represent this expression is given by:-








e- If regular expression R contain P*, then the transition diagram that represent this expression is given by:-











2- Substitute the primitive components in regular expression to get an NFA




Example: Convert the regular expression into an NFA.
R= abc?d*
1) The primitive component for this regular expression
(a) a.b.c that can be converted into:-




(b) d* that can be converted into:-







2) Substitute the primitive components to get:-