[go: up one dir, main page]

0% found this document useful (0 votes)
112 views66 pages

Can We Build A Finite Automaton For Every Regular Expression?, - Build FA Based On The Definition of Regular Expression

The document discusses finite automata (FA) and regular expressions (RE). It explains that a nondeterministic finite automaton (NFA) can have epsilon transitions and multiple transitions per state, while a deterministic finite automaton (DFA) has a single transition per state. The key ideas are: 1) NFAs and DFAs recognize the same regular languages. DFAs are easier to implement but NFAs can be simpler. 2) Thompson's construction builds an NFA for a RE by combining NFA patterns for symbols and operators with epsilon transitions. 3) The subset construction algorithm converts an NFA to an equivalent DFA by using sets of NFA states for each DFA state and transition

Uploaded by

tariqravian
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
112 views66 pages

Can We Build A Finite Automaton For Every Regular Expression?, - Build FA Based On The Definition of Regular Expression

The document discusses finite automata (FA) and regular expressions (RE). It explains that a nondeterministic finite automaton (NFA) can have epsilon transitions and multiple transitions per state, while a deterministic finite automaton (DFA) has a single transition per state. The key ideas are: 1) NFAs and DFAs recognize the same regular languages. DFAs are easier to implement but NFAs can be simpler. 2) Thompson's construction builds an NFA for a RE by combining NFA patterns for symbols and operators with epsilon transitions. 3) The subset construction algorithm converts an NFA to an equivalent DFA by using sets of NFA states for each DFA state and transition

Uploaded by

tariqravian
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 66

RE → Finite Automata

 Can we build a finite


automaton for every regular
expression?
 Yes, – build FA inductively
based on the definition of
Regular Expression
1
NFA
Nondeterministic Finite
Automaton (NFA)
 Can have multiple
transitions for one input
in a given state
 Can have  - moves
2
Epsilon Moves
 ε – moves
machine can move from state
A to state B without consuming
input

A B

3
NFA
operation of the automaton is not
completely defined by input
1
0 1
A B C

On input “11”, automaton could be


in either state
4
Execution of FA
A NFA can choose
 Whether to make -moves.
 Which of multiple transitions
to take for a single input.

5
Acceptance of NFA
 NFA can get into multiple states
 Rule: NFA accepts if it can get
in a final state
1
0 1
A B C

0
6
DFA and NFA
Deterministic Finite Automata
(DFA)
 One transition per input per
state.
 No  - moves

7
Execution of FA
A DFA
 can take only one path
through the state graph.
 Completely determined by
input.
8
NFA vs DFA
 NFAs and DFAs recognize
the same set of languages
(regular languages)
 DFAs are easier to
implement – table driven.

9
NFA vs DFA
 For a given language, the
NFA can be simpler than
the DFA.
 DFA can be exponentially
larger than NFA.

10
NFA vs DFA
 NFAs are the key to
automating RE → DFA
construction.

11
RE → NFA Construction
Thompson’s construction
( 1968)
 Build an NFA for each RE
term.
 Combine NFAs with
-moves.
12
RE → NFA Construction
Key idea:
 NFA pattern for each
symbol and each operator.
 Join them with -moves in
precedence order.

13
RE → NFA Construction
a
s0 s1
NFA for a

a  b
s0 s1 s3 s4

NFA for ab
14
RE → NFA Construction
a
NFA for a s0 s1

15
RE → NFA Construction
a
NFA for a s0 s1
b
NFA for b s3 s4

16
RE → NFA Construction
a
NFA for a s0 s1
b
NFA for b s3 s4

a b
s0 s1 s3 s4

17
RE → NFA Construction
a
NFA for a s0 s1
b
NFA for b s3 s4

a  b
s0 s1 s3 s4

NFA for ab
18
RE → NFA Construction
a
 s1 s2 
s0 s5
 b
s3 s4 

NFA for a | b
19
RE → NFA Construction
a
s1 s2

NFA for a
20
RE → NFA Construction
a
s1 s2

b
s3 s4

NFA for a and b


21
RE → NFA Construction
a
 s1 s2 
s0 s5
 b
s3 s4 

NFA for a | b
22
RE → NFA Construction

 s1
a 
s0 s2 s4


NFA for a*
23
RE → NFA Construction

a
s1 s2

NFA for a
24
RE → NFA Construction

 s1
a 
s0 s2 s4


NFA for a*
25
Example RE → NFA
NFA for a ( b|c )* 

b
   s4 s5 
a 
s0 s 1 s2 s3 s8 s9
 s c
6 s7 


26
Example RE → NFA
building NFA for a ( b|c )*

a
s0 s1

27
Example RE → NFA
NFA for a, b and c

b
s4 s5
a
s0 s1
c
s6 s7

28
Example RE → NFA
NFA for a and b|c

b
 s4 s5 
a
s0 s1 s3 s8
 s c
6 s7 

29
Example RE → NFA
NFA for a and ( b|c )*

b
  s4 s5 
a 
s0 s 1 s2 s3 s8 s9
 s c
6 s7 


30
Example RE → NFA
NFA for a ( b|c )* 

b
   s4 s5 
a 
s0 s 1 s2 s3 s8 s9
 s c
6 s7 


31
NFA → DFA Construction
 The algorithm is called subset
construction.
 In the transition table of an
NFA, each entry is a set of
states.
 In DFA, each entry is a single
state
32
NFA → DFA Construction
 The general idea behind
NFA-to-DFA construction is
that each DFA state
corresponds to a set of
NFA states.

33
NFA → DFA Construction
 The DFA uses its state to
keep track of all possible
states the NFA can be in
after reading each input
symbol.

34
NFA → DFA Construction
 We will use the following
operations.
 -closure(T):
set of NFA states reachable
from some NFA state s in T
on -transitions alone.
35
NFA  DFA Construction
 move(T,a):
set of NFA states to which
there is a transition on input
a from some NFA state s in
set of states T.

36
NFA → DFA Construction
 Before it sees the first input
symbol, NFA can be in
any of the state in the set
-closure(s0), where s0 is the
start state of the NFA.

37
NFA → DFA Construction
 Suppose that exactly the
states in set T are
reachable from s0 on a
given sequence of input
symbols.

38
NFA → DFA Construction
 Let a be the next input
symbol.
 On seeing a, the NFA can
move to any of the states in
the set move(T,a).

39
NFA → DFA Construction
 Let a be the next input
symbol.
 On seeing a, the NFA can
move to any of the states in
the set move(T,a).

40
NFA → DFA Construction
 When we allow for
-transitions, NFA can be in
any of the states in
-closure(move(T,a))
after seeing a.

41
Subset Construction
Algorithm:
Input:
NFA N with state set S,
alphabet , start state
s0, final states F
42
Subset Construction
Output:
DFA D with state set S’,
alphabet , start states
s0’ = -closure(s0), final
states F’, transition
table: S’ x  → S’
43
Subset Construction Example

a
2 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

NFA for (a | b )*abb
44

a
2 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 The start state of equivalent
DFA is -closure(0), which is
A = {0,1,2,4,7}
45

2 a
3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 A = {0,1,2,4,7}, these are
exactly the states reachable
from state 0 via -transition.
46

2 a 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 The input symbol alphabet


here is {a,b}.
47

2 a 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 The algorithm tells us to mark
A and then compute
-closure(move(A,a))
48

2 a
3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 move(A,a)), is the set of states
of NFA that have transition on
‘a’ from members of A.
49

2 a
3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 Only 2 and 7 have such


transition, to 3 and 8.
50

2 a 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 So, -closure(move(A,a)) =
-closure({3,8}) =
{1,2,3,4,6,7,8}
51

2 a 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 Let B = {1,2,3,4,6,7,8}.
 Thus Dtran[A,a] = B
52

2 a 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 For input b, among states in A,
only 4 has transition on b to 5
53

2 a 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 C = -closure({5})
= {1,2,4,5,6,7}
 Thus, Dtran[A,b] = C
54

a
2 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 We continue this process with


the unmarked sets B and C
55

a
2 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 i.e., -closure(move(B,a)),
-closure(move(B,b)),
56

2 a 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 -closure(move(C,a)) and
-closure(move(C,b))
57

a
2 3
 
  a b b
0 1 6 7 8 9 10
 
b
4 5

 Until all sets and states of DFA
are marked.
58
Subset Construction
Eventually, the 5 sets are:
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
E={1,2,4,5,6,7,10}
59

a
2 3
 
  a b b
0 1 6 7 8 9 10
 b

4 5

A is start state
A={0,1,2,4,7} D={1,2,4,5,6,7,9}
B={1,2,3,4,6,7,8} E={1,2,4,5,6,7,10}
C={1,2,4,5,6,7}
60

2 a 3
 
  a b b
0 1 6 7 8 9 10
 b

4 5

E is accepting state
A={0,1,2,4,7} D={1,2,4,5,6,7,9}
B={1,2,3,4,6,7,8} E={1,2,4,5,6,7,10}
C={1,2,4,5,6,7}
61
Resulting DFA
a a
a b b
A B D E
a
b a
b
C

b
DFA for (a | b )*abb
62
Resulting DFA
a a
a b b
A B D E
a
b a
b
C

b a a a a b b
63
Final Transition Table
Input symbol
State a b

A B C
B B D
C B C
D B E
E B C 64
DFA Minimization
a a
a b b
A B D E
a
b a
b
C

b
DFA for (a | b )*abb
65
DFA Minimization
b a a
a b b
A,C B D E
a
b

Minimized DFA for (a | b )*abb

66

You might also like