Transcript q 3

CSCI 2670
Introduction to Theory of
Computing
September 11, 2007
Agenda
• Last class
– Discussed non-determinism
– Equivalence of DFA’s and NFA’s
• Today
– Further exploration of equivalence of
DFA’s and NFA’s
• Tomorrow
– Closure of regular languages under
regular operators
– Another method for describing regular
languages
1
0
{q1}
{q2,q3}
{q2}

{q3}

{q1,q2} {q2,q3}
{q1,q3} {q2,q3}
{q2,q3}

{q1,q2,q3} {q2,q3}


0
Example
1

{q1,q3}

{q1,q3}

{q1,q3}
{q1,q3}

q2
q1
1
0
q3
{q2,q3}
0
{q1}
0
1
0
1
1

0,1
What about ε jumps?
• For each R  P(Q), define function
E(R)
E(R) = {q | q can be reach by 0 or more ε
jumps from some r  R}
• Redefine ’(R,a) to include E(R)
’(R,a) = {q | q  E((r,a)) for some r  R}
• Are we done?
No! What if there are  jumps from q0?
q0’ = E({q0})
Closure of NFA’s under regular operations
• Recall the following are the regular
operators
– Union
– Concatenation
– Kleene star
Union is a regular operation
Theorem: The class of regular
languages is closed under the union
operation
Proof approach: Assume A1 and A2 are
both regular languages with A1=L(M1)
and A2=L(M2) and create an NFA M
such that L(M) = A1A2
Method: Proof by construction
Construct M from M1 and M2
ε
M1
ε
M2
M
Concatenation is a regular operation
Theorem: The class of regular
languages is closed under the
concatenation operation
Proof approach: Assume A1 and A2 are
both regular languages with A1=L(M1)
and A2=L(M2) and create an NFA M
such that L(M) = A1A2
Method: Proof by construction
Construct M from M1 and M2
M1
ε
ε
M2
M
Kleene star is a regular operation
Theorem: The class of regular
languages is closed under the Kleene
operation
Proof approach: Assume A1 is a regular
language with A1=L(M1) and create an
NFA M such that L(M) = A1*
Method: Proof by construction
Construct M from M1
ε
ε
ε
M1
M
Regular expressions (RE’s)
• So far we have had to describe
languages either with finite automata
or with words
– Potentially clumsy or imprecise
• Today we learn precise expression to
describe regular languages
– Example: All strings with at least one 1
becomes *{1}*, or more simply *1*
Where have you seen RE’s?
•
•
•
•
Grep
Awk
Perl
Search expressions within emacs or vi
RE inductive definition
R is a regular expression if R is
Abuse of
1. a for some a  
notation.
2. ε
These should
be sets!
3. 
4. R1  R2 where R1 and R2 are both
regular expressions
5. R1  R2 where R1 and R2 are both
regular expressions
6. (R1*) where R1 is a regular expression
Examples
• 0*10*10*
– {w | w contains exactly two 1’s}
• *11*
– {w | w contains two consecutive 1’s}
• *1(0ε)1*
– {w | w contains two 1’s separated by at
most one 0}
• (0ε)(1ε)
– {0,1,01,ε}
RE’s and regular languages
Theorem: A language is regular if and
only if some regular expression
describes it.
– i.e., every regular expression has a
corresponding DFA and vice versa
RE’s and regular languages
Lemma: If a language is described by a
regular expression, then it is regular.
– find an NFA corresponding to any
regular expression
– use inductive definition of RE’s
1. R=a for some a
q1
a
q2
N = {{q1,q2},,,q1,{q2}} where (q1,a)={q2}
and (r,x)= whenever r=q2 or x≠a
2. R=ε
q1
N = {{q1},,,q1,{q1}} where (q1,x)= for
all x
3. R=
q1
N = {{q1},,,q1,} where (q1,x)= for
all x
Remaining constructions
•
•
•
•
R = R1R2
R = R1R2
R = R1*
These were all shown to be regular
operators
– We know we can construct NFA’s for R
provided they exist for R1 and R2
Example
• R = 1
– R = (01)1
R1 = 0
0
R2 = 1
1
R3 = 01
0
ε
1
ε
R = Σ1
ε
ε
0
1
ε
ε
1
Example2
• R = 1(0ε)*
R1 = 1
1
R2 = 0ε
0
ε
ε
ε
ε
R = 1(0ε)*
1
0,1
R3 = *
ε
ε
ε
0
ε
ε
ε
0,1
ε
Equivalence of RE’s and DFA’s
• We have seen that every RE has a
corresponding NFA
– Therefore, every RE has a corresponding
DFA
– I.e, every RE describes a regular language
• We need to show that every regular
language can be described by a RE
• Begin by converting all DFA’s into
GNFA’s
– Generalized Non-deterministic Finite
Automata
GNFA’s
•
A GNFA is an NFA with the
following properties:
1. The start state has transition arrows
going to every other state, but no
arrows coming in from any other state
2. There is exactly one accept state and
there is an arrow from every other
state to this state, but no arrows to
any other state from the accept state
3. The start state is not the accept state
GNFA’s (continued)
4. Except for the start and accept
states, one arrow goes from every
state to every other state and also
from each state to itself
5. Instead of being labeled with symbols
from the alphabet, transitions are
labeled with regular expressions
Example GNFA
01
 0
1


0
10

Equivalence of DFA’s and RE’s
• First show every DFA can be
converted into a GNFA that accepts
the same language
• Then show that any GNFA has a
corresponding RE that accepts the
same language
Converting a DFA into a GNFA
• Add two new states
– New start state with an ε jump to the
original DFA’s start state
– New accept state with an ε jump from
each of the original DFA’s accept states
• This new state will be the only accept state
• All transition labels with multiple
labels are relabeled with the union of
the previous labels
• All pairs of states without transitions
get a transition labeled 
Converting a DFA to a GNFA
0
1
qs
ε
q1
q2
1
0
q3
ε
0,1
q4
0,1
Add two new states
qt
Converting a DFA to a GNFA
0
1
qs
ε
q1
q2
1
0
q3
ε
0,1
01
q4
qt
0,1
01
• All transition labels with multiple
labels are relabeled with the union of
the previous labels
Converting a DFA to a GNFA
0
1
qs
ε
q1
q2
1
0
q3
ε
01
q4
qt
01
• All pairs of states without transitions
get a transition labeled 