Transcript Document

Lecture3 DFA vs. NFA, properties
of RL
 2004 SDU
Regular operations
They are used to study the properties of regular languages.
Let A and B be languages, define the regular operations
union, concatenation, and star as follows:
•Union: AB = {x| x  A or x  B}
•Concatenation: A  B = {xy | x  A and y  B}
•Star: A* = {x1x2…xk | k  0 and each xi  A }
Example: A = {good, bad}, B = {boy, girl}
Then AB = {good, bad, boy, girl}; A  B ={goodboy,
goodgirl, badboy, badgirl}, and
A*={, good, bad, goodgood, goodbad, badgood, badbad,
goodgoodgood, goodgoodbad, goodbadgood,
goodbadbad,…}
 2004 SDU
2
Closure properties of Regular
Languages
Regular languages are closed under:
 Union   if A and B are regular languages,
so is A  B
 Concatenation  if A and B are regular
languages, so is A  B
 Star * if A is a regular language, so is A*.
 2004 SDU
3
General Construction for  and 
Let A1 and A2 be two regular languages, and M1 and M2 be the DFAs
that recognize them, we want to construct a DFA M to recognize A1
 A2.
Can M first simulate M1 and then simulate M2 on an given input?
Idea: Simulate two DFA's simultaneously.
Let M1 = (Q1, , 1, s1, F1) and M2 = (Q2, , 2, s2, F2)
Define:M = (Q, , , s, F) where:
 Q = Q1  Q2
 s = (s1, s2)
 ((q1, q2), ) = (1(q1, ), 2(q2, )), for each (q1, q2)Q, and each

For Union, F = ? The proof?
 Ans: (Q1  F2)  (F1  Q2)
For Intersection, F = ? The proof?
 Ans: F1  F2
 2004 SDU
4
Example of union
L1={w{0,1}*| w contains 01 as substring}
L2={w{0,1}*| w contains 10 as substring}
1
1
0
0
1
4
0
2
5
1
3
0
6
1
0
14 0
1
1
24
0,1
0,1
0
34
1
1 1
1
15
25 1 35
0
0 0 1
0,1
16 0
36
26
0
 2004 SDU
-redundant states
You can construct M in an
inductive way and avoid
redundancy!
1. (s1, s2)  Q
2. If (q1, q2)  Q, then
((q1,0), (q2,0))  Q
((q1,1), (q2,1))  Q
5
How about the other regular
operations
The concatenation  ?
The star * ?
Can we use similar way?
To solve this problem, we introduce a new technique 
non-determinism.
 In deterministic computation, the next state is determined
 In non-deterministic computation, several choices may exist
 Page 48 for example, and 49 for clarity
 2004 SDU
6
An example of NFA
0,1
q1 1
q2 0, q3
1
q4
0,1
What is the difference between DFA and NFA?
How does it compute on input 001100?
 2004 SDU
7
Formal definition of DFA
A DFA is a 5-tuple: M = (Q, , , s, F)
Where,




Q is finite set of states
 is finite input alphabet
s  Q is the initial state
F  Q is the set of final states
 : Q   -> Q // note that this is a function
 2004 SDU
8
Nondeterministic Finite
Automaton (NFA)
Generalization of DFA. Allows:
 0 or more next states for the same (q, a).
– Guessing
 Transitions labeled by the empty string .
– Changing state without reading input
Motivation: Flexibility, simplicity.
 2004 SDU
9
Formal definition of NFA
Notation:   =   {}.
An NFA is a 5-tuple: M = (Q, , , s, F) where:





Q - a finite set of states
 - a finite alphabet
s – the start state
F  Q – the set of final states
 : Q     P(Q), the power set of Q.
 2004 SDU
10
NFA -definition
Let N =(Q, , , q0, F) be an NFA and w a string over the alphabet .
We say N accepts w if we can write w as w = y1…ym ,where each yi
is a member of  and a sequence of states p0,…, pm exists with
three conditions:
1. p0=q0;
2. for every i, 1 i  m, pi(pi-1,yi);
3. pm F
Language recognized by an NFA N, denoted as L(N), is the set
of the strings accepted by N.
 2004 SDU
11
Example of NFA
0

0

0
An NFA that accepts all strings
of 0’s the number of which
is either a multiple of 2 or a multiple
of 3.
guess
0
0
check
Pr: How to understand some branch dies?
The formal description of this NFA is…?
The computing process on input 0000 is…?
more examples on pages 48, 51
 2004 SDU
12
NFA vs. DFA
Is NFA more powerful than DFA?
 Ans: No.
Theorem:
 For every NFA M there is an equivalent DFA M'
Proof Idea:
 NFA is in a set of states at any point during reading a string.
 DFA will use a state to keep track of this.
Important Assumption:
 No transition labeled by epsilon.
(Will get rid of this assumption later.)
 2004 SDU
13
Equivalent DFA construction.
NFA N = (Q, , , s, F)
DFA M = (Q', , , s', F') where:
 Q' = p(Q), power set of Q
 s' = {s}
 F' = {P  Q' | P  F is nonempty}
 ({q1,…,qm}, a) = (q1, a)  (q2, a)  ...  (qm, a)
i.e. find all the states that can be reached on a from
all the NFA states in a DFA state.
 2004 SDU
14
How to handle epsilon
transitions?
Define e-closure of state P, E(P) = {q|q can be reached from some
p  P by traveling along 0 or more  arrows}.
Let: ({q1,…,qm}, a) = {qQ| q  E((q1, a))  E((q2, a))  ...
 E((qm, a))
Let: s’=E(s)
Proof: at each step of M on an input, it clearly enters a state that
corresponds to the subset of states that N could be in at that point.
See page56.
See page 57, example1.41
 2004 SDU
15
Construct DFA from NFA

………………………….w1


…………………….w2
…
…
……………………..wn

…

is an accepting path on w1…wn in NFA
is an accepting path on w1…wn in DFA
 2004 SDU
16
Construct from NFA to DFA (example)
1
b
a
2
a,b
a
a,b


3
a
{1}
b
b
{3}
a
{1,3}
b
 2004 SDU
b
b
a
{1,2}
{2}
a
{2,3}
a,b
a
a
b
{1,2,3}
17
Regular languages
Conclusion: A language is regular iff some NFA
recognizes it.
 2004 SDU
18
Construction for LºL‘
page 60
Let L=(Q1, , 1,s1,F1); L’=(Q2, , 2,s2,F2)
Define:
L’’ = (Q,,,s,F), where
Q = Q1  Q2
s = s1
F = F2
1 (q, a), if q  Q1 , and q  F1;
 (q, a), if q  Q ;
 2
2
 ( q, a )  
1 (q,a), if q  F1 , a  
 1 (q,a)  {s 2 },if q  F1 , a  
 2004 SDU
19
N’
N
N’’



 2004 SDU
20
L*
Let L=(Q1, , 1, s1, F1)
1 (q, a), if q  Q1 and q  F1;
 (q, a), if q  F and a   ;
L* = (Q, , , s, F)
1
Q = {s}  Q1
 1
F = {s}  F1 ( q, a )   ( q, a )  {s }, if q  F and a   ;
 1
1
1
{s }, if q  s and a   ;
 1

 ,if q  s and a  
Define:
 2004 SDU
21
N*
N



 2004 SDU
22