Deterministic Automata

The NFA shown in Fig. (10) has more than one transition from state 0 on input
a, that is, it may go to state 0 or 1. Similarly, the NFA of Fig.11 has two transitions
on  from state 0. These situations are the reason why it is hard to simulate an NFA
with a computer program. The deterministic finite automata have at most one
path from the start state labeled by any string. The finite automaton is
deterministic if
1- It has no transitions on input 
2- For each state s and input symbol a, there is at most one edge labeled a leaving
s.

Example: in Fig.12 below we see a Deterministic Finite Automata (DFA)

accepting the language (ab)*abb, which is the same language as that accepted by
the NFA of Fig. (9)
b b

Start
a b b
0 1 2 3
a
a a
Fig. (12): DFA accepting (ab)*abb
Since there is at most one transition out of any state on any symbol, a DFA is
easier to simulate by a program than an NFA.

How to Build a Lexical Analyzer

Step1 Convert the Grammar into Transition Diagram.

Step2 Convert the Regular Expression into Nondeterministic Finite State
Automata.
Step3 Convert the NFA into DFA.
Step4 Minimize Finite State Automata.
Step5 Write an efficient program for the minimized finite state automata, called
(minimized finite state automata recognizer).
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.
Formal definition for finite automaton
M is a 5-tuple, (Q, Σ, δ, q0, F), consisting of
 a finite set of states (Q)
 a finite set of input symbols called the alphabet (Σ)
 a transition function (δ : Q × Σ → Q)
 a start state (q0 ∈ Q)
 a set of accept states (F ⊆ Q)

Example: convert the following grammar into transition diagram:

G=({S, R, U},{a, b, c}, P, {S}, {Z}) 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. (13)
 b

a c
Z S R
c
b
a
b c

U a b
Y X

Fig. (13): Transition Diagram

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> ● <integer>
<integer>::= <digit><integer> <digit>
<digit>::= 012…9
We use the following steps:-
1- Construct a separate transition diagram for every grammar.

<Real number>:
●
<integer> <integer>
------------- 1

< Integer>:
<digit>
------------- 2

<digit>
<digit>:
0

1 ------------- 3
.
.
.
9
2- Substitute every non terminal with its transition diagram
(a) Substitute the non terminal <integer> in transition diagram 1 with the
transition diagram 2

<digit> . <digit>

<digit> <digit>

(b) Substitute the non terminal <digit> with transition diagram 3

Start
0
0…9
1
. 2
0…9
3

0…9 0…9

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.


i f
b- If there exist a terminal Symbol 'a' in , we construct the NFA:-

a
i1 f1

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.
 Sp Fp
 

i f

 
SQ FQ

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

Fp
Sp SQ
FQ

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

i
 Sp
P fp  f


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:-
a b c
1 2 3 4
d* that can be converted into:-


5
 6
d
7
 8


2) Substitute the primitive components to get:-
a b c
1 2 3 4



0 9




 d 
5 6 7 8

Examples:
A grammar is regular if and only if γ is a single nonterminal and α is a single
terminal or a single terminal followed by a single nonterminal, that is a production
is of the form
X → a or X → aY,

Where X and Y are nonterminal and a is a terminal.

A regular grammar is any right-linear or left-linear grammar

Right-Linear Grammars Left-Linear Grammars

All productions have form: All productions have form:
A→ xB A→Bx
or or
A→ x A→ x
x is string of terminals x is string of terminals
1.
∑ = {a, b}, V = {S} and P = {S → aS, S → bS, S → Ʌ}

Where Ʌ empty string

2.
∑ = {a, b}, V = {S} and P = {S → aS, S → bS, S → a, S → b}
3.
Example: The grammar with the following productions:
S →aX
X →Sb
S → λ
Is linear but neither right-linear nor left-linear, and thus not a regular grammar.

Example:
Let us construct an NFA for r = (a|b)*abb.
For subexpressions rl, the first a, we construct the NFA:
a
Start 2 3

State numbers have been chosen for consistency with what follows. For r2 we
construct
b
Start 4 5

We can now combine N(r1) and N(r2), using the construction of figure below to
obtain the NFA for r3 = r|r2; this NFA is shown below
a
2 3
 

Start
1 6

 
4 5
b

The NFA for r4 = (r3)* is then as shown in below

 

a
2 3

  
Start
0 1 6 7
 
4 5
b


We construct the NFA for abb as figure below

a b b
8 9 10

We eventually construct the NFA for (a|b)*abb in figure below

a
2 3

  
Start a b
0 1 6 7 8 b 9 10



4 5
b


Decomposition of (ab|ba)a*