Scribd
Upload
62 views25 pages

CS5371 Theory of Computation: Lecture 6: Automata Theory IV (Regular Expression NFA DFA)

This document discusses the equivalence between regular expressions, non-deterministic finite automata (NFA), and deterministic finite automata (DFA) in describing languages. It provides formal definitions of regular expressions and shows how to construct an NFA from a regular expression through six cases. It then proves that if a language is described by a regular expression, it is regular by constructing an NFA, and vice versa by converting an NFA to a regular expression. The conversion involves first changing the NFA to a generalized NFA (GNFA) and then removing states from the GNFA one by one.

Uploaded by

Kamal Walia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
62 views25 pages

CS5371 Theory of Computation: Lecture 6: Automata Theory IV (Regular Expression NFA DFA)

This document discusses the equivalence between regular expressions, non-deterministic finite automata (NFA), and deterministic finite automata (DFA) in describing languages. It provides formal definitions of regular expressions and shows how to construct an NFA from a regular expression through six cases. It then proves that if a language is described by a regular expression, it is regular by constructing an NFA, and vice versa by converting an NFA to a regular expression. The conversion involves first changing the NFA to a generalized NFA (GNFA) and then removing states from the GNFA one by one.

Uploaded by

Kamal Walia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 25

CS5371

Theory of Computation
Lecture 6: Automata Theory IV
(Regular Expression = NFA = DFA)
Objectives
•Give formal definition of Regular
Expression
•Show that the power of Regular
Expression = the power of NFA = the
power of DFA
–in terms of describing a language
Regular Expression
(Formal Definition)
•We say R is a regular expression if R is
– a for some a in the alphabet , or
– , or Don’t confuse with ;
– ;, or
– (R1 [ R2), where R1 and R2 are regular
expressions, or
– (R1 o R2), where R1 and R2 are regular
expressions, or
– (R1*), where R1 is a regular expression
True or False?
•R [ ; = R True

•R o = R True

•R [ = R False

•R o ; = R False
Equivalence with NFA
(Part I)
Lemma: If a language is described by a
regular expression, then it is regular.

Proof: Let R be the regular expression


and L be the language described by R.
Note: L is sometimes written as L(R)
We show how to convert R into an NFA
recognizing L(R).
Six Cases to Consider

(1) R = a for some a in the alphabet .


Then L(R) = {a}, and the following
NFA recognizes L(R)

a
(2) R = . Then L(R) = {
}, and the
following NFA recognizes L(R)

(3) R = ;. Then L(R) = { }, and the


following NFA recognizes L(R)
For the last three cases:
(4) R = R1 [ R2
(5) R = R1 o R2
(6) R = R1*
we use the constructions given in the
proofs that the class of regular language
is closed under the regular operations.
–In other words, we construct NFA for R
from NFA for R1 and NFA for R2
Converting R to NFA (Example)

R = (ab [ a)*
a
a

b
b

a  b
ab
ab [ a
a  b

 a


(ab [ a)*
a  b


 a


Equivalence with NFA
(Part II)
Lemma: If a language is regular, it can be
described by a regular expression.

Proof: Let L be the regular language. We


will convert the DFA for L into a regular
expression. First, we introduce a new
type of automaton: the generalized non-
deterministic finite automaton (GNFA)
Later, we show DFA  GNFA  Reg Ex
GNFA (Example)
aa
ab*
qstart

a*
ab [ ba
;
(aa)*

b* qaccept

ab
b
GNFA
•Similar to NFA, except that the labels on
the transition arrows are regular
expressions (instead of a character or  )
•To move along a transition arrow, we read
blocks of characters such that it matches
the description of the regular expression
on that arrow
•An input string is accepted if there is a
way to read the input string such that the
GNFA is in an accepting state after
processing the whole input string
GNFA (further assumptions)
•Only one start state qstart, with no
incoming arrows
•Only one accepting state qaccept, with
no outgoing arrows
•Each state (except qstart and qaccept)
has exactly one arrow going to every
other state and also itself
Back to the Proof:
Converting DFA to GNFA
•Add a new start state, with arrow to the
original start state
•Add a new accept state, with arrow from
each of the original accept state
•If original arrow has multiple labels, we
replace this with a new arrow whose label
is a regular expression formed by the union
of the labels
•If originally no arrow between two states,
we add a new arrow whose label is ;
Converting DFA to GNFA
(Example)
a a
b b
a a

b
a
b
a

b b

DFA GNFA
Converting GNFA
to Regular Expression
•We iteratively remove one state in
GNFA, such that after each state
removal, the new GNFA obtained will
recognize the same language as the
previous one
•When the number of states of GNFA
is 2, we have the regular expression
(why??)
How to remove a state?
•Select any state q except qstart and
qaccept
•Remove q
–To compensate the absence of q, the
new label on the arrow from qi to qj
becomes a regular expression that
describes all strings that would take the
GNFA to go from qi to qj, either directly
or via q
How to remove a state?
R4

qi qj
R4 [ (R1) (R2)*(R3)
qi qj
R1 R3
q

R2

Before Removal After Removal


Previous Example
a aa [ b
b a
a

 ?
b
a
 ? 
b
b
 
?

Before Removal After Removal


Previous Example

a aa [ b
?
ab

b ba [ a ? ?

bb ?

Before Removal After Removal


Previous Example
Before Removal: a(aa [ b)*

a(aa [ b)*ab [ b (ba [ a) (aa [ b)* [ 

(ba [ a) (aa [ b)* ab [ bb


After Removal:
?
Final Step

(a(aa [ b)*ab [ b)((ba [ a) (aa [ b)* ab [ bb)*


((ba [ a) (aa [ b)* [ 
) [ a(aa [ b)*
What we have learnt so far
•DFA = NFA
–proof by construction
•Regular Expression = DFA
–proof by construction
•Pumping Lemma
–proof by contradiction
•Existence of Non-regular Languages
–pumping lemma
Next Time
•Context Free Grammar
–A more powerful way to describe a
language

You might also like