Single Final State for NFAs

Riphah International University FSD 1

Any NFA can be converted

to an equivalent NFA

with a single final state

Riphah International University FSD 2

 Example
a
NFA
a b

a Equivalent NFA

a b

b 

Riphah International University FSD 3
 In General
NFA

Equivalent NFA

 Single
 final state
Riphah International University FSD 4
 Extreme Case

NFA without final state

Add a final state

Without transitions

Riphah International University FSD 5

 Properties of
Regular Languages

Riphah International University FSD 6

For regular languages L1 andL2
we will prove that:

Union: L1  L2
Concatenation: L1L2
Star: L1 * Are regular
Languages
R
Reversal: L1
Complement: L1
Intersection: L1  L2
Riphah International University FSD 7
e say: Regular languages are closed unde

Union: L1  L2
Concatenation: L1L2
Star: L1 *
R
Reversal: L1
Complement: L1
Intersection: L1  L2
Riphah International University FSD 8
Regular language L1 Regular languageL2

LM1  L1 LM 2  L2

NFA M1 NFA M2

Single final state Single final state

Riphah International University FSD 9
 Example
M1
n 0
a
n
L1 {a b} b

M2
b a
L2 ba

Riphah International University FSD 10

 Union
NFA for L1  L2
M1

 

 M2 

Riphah International University FSD 11

 Example
n
NFA for L1  L2 {a b}  {ba}
n
L1 {a b}
a
b
 

 L2 {ba} 
b a
Riphah International University FSD 12
 Concatenation

NFA for L1L2

M1 M2
 

Riphah International University FSD 13

 Example

n n
NFA for L1L2 {a b}{ba} {a bba}

n
L1 {a b}
a
L2 {ba}
b  b a 

Riphah International University FSD 14

 Star Operation
NFA for L1 *

  L1 *
M1
 


Riphah International University FSD 15
 Example

n w w1w2  wk
NFA for L1* {a b} * wi  L1

n
L1 {a b}
a
 b 


Riphah International University FSD 16
 Reverse
R
NFA for L1
L1 M1 M1

1. Reverse all transitions

2. Make initial state final state

and vice versa
Riphah International University FSD 17
 Example
M1
a
n
L1 {a b} b

M1
a
R n
L1 {ba } b

Riphah International University FSD 18

 Complement

L1 M1 L1 M1

1. Take the DFA that acceptsL1

2. Make final states non-final,

and vice-versa
Riphah International University FSD 19
 Example
M1
a a, b
n b a, b
L1 {a b}

M1
n a a, b
L1 {a, b} *  {a b}
b a, b

Riphah International University FSD 20

 Intersection
DeMorgan’s Law: L1  L2 L1  L2
L1 , L2 regular
L1 , L2 regular
L1  L2 regular
L1  L2 regular
L1  L2 regular
Riphah International University FSD 21
 Example

n
L1 {a b} regular
L1  L2 {ab}
L2 {ab, ba} regular regular

Riphah International University FSD 22

Regular Expressions

Riphah International University FSD 23

 Regular Expressions
Regular expressions
describe regular languages

Example: (a  b c) *

describes the language

a, bc*  , a, bc, aa, abc, bca,...

Riphah International University FSD 24

 Recursive Definition
Primitive regular expressions: ,  , 

Given regular expressions r1 andr2

r1  r2
r1 r2
Are regular expressions
r1 *
r1 
Riphah International University FSD 25
 Examples

A regular expression: a  b c * (c   )

Not a regular expression: a  b 

Riphah International University FSD 26

 Languages of Regular Expressions

Lr  : language of regular expression

r

Example
L(a  b c) *  , a, bc, aa, abc, bca,...

Riphah International University FSD 27

 Definition

For primitive regular expressions:

L  

L   

La  a
Riphah International University FSD 28
 Definition (continued)

For regular expressionsr1 r2

and

Lr1  r2  Lr1  Lr2 

Lr1 r2  Lr1  Lr2 

Lr1 * Lr1 *

Lr1  Lr1 
Riphah International University FSD 29
 Example
a  b a *
Regular expression:

La  b a * La  b  La *

La  b  La *
La  Lb  La *
a  b a*
a, b  , a, aa, aaa,...
a, aa, aaa,..., b, ba, baa,...
Riphah International University FSD 30
 Example

Regular expression r a  b * a  bb 

Lr  a, bb, aa, abb, ba, bbb,...

Riphah International University FSD 31

 Example

Regular expression r aa * bb * b

2n 2m
Lr  {a b b : n, m 0}

Riphah International University FSD 32

 Example

Regular expression r (0  1) * 00 (0  1) *

L(r )= { all strings with at least

two consecutive 0 }

Riphah International University FSD 33

 Example

Regular expression r (1  01) * (0   )

L(r )= { all strings without

two consecutive 0 }

Riphah International University FSD 34

 Equivalent Regular Expressions

Definition:

Regular expressionsr1 andr2

are equivalent ifL( r1 ) L( r2 )

Riphah International University FSD 35

 Example
L= { all strings without
two consecutive 0 }

r1 (1  01) * (0   )
r2 (1* 011*) * (0   )  1* (0   )

r1 and r2
L(r1 ) L(r2 ) L
are equivalent
regular expr.
Riphah International University FSD 36
Regular Expressions
and
Regular Languages

Riphah International University FSD 37

 Theorem

Languages
Generated by
Regular Expressions
 Regular
Languages

Riphah International University FSD 38

 Theorem - Part 1

Languages
Generated by  Regular
Languages
Regular Expressions

1. For any regular expressionr

the language L(r ) is regular

Riphah International University FSD 39

 Theorem - Part 2

Languages
Generated by  Regular
Languages
Regular Expressions

2. For any regular language L there is

a regular expression r with L( r ) L

Riphah International University FSD 40

 Proof - Part 1

1. For any regular expressionr

the language L(r ) is regular

Proof by induction on the size of r

Riphah International University FSD 41

 Induction Basis
,
Primitive Regular Expressions: , 
NFAs

L( M1 )  L( )

regular
L( M 2 ) {} L( )
languages
a
L( M 3 ) {a} L(a )

Riphah International University FSD 42

 Inductive Hypothesis

Assume
for regular expressions r1 andr2
that
L(r1 ) and L(r2 ) are regular languages

Riphah International University FSD 43

 Inductive Step
We will prove:
Lr1  r2 

Lr1 r2 
Are regular
Languages
Lr1 *

Lr1 
Riphah International University FSD 44
By definition of regular expressions:

Lr1  r2  Lr1  Lr2 

Lr1 r2  Lr1  Lr2 

Lr1 * Lr1 *

Lr1  Lr1 
Riphah International University FSD 45
By inductive hypothesis we know:
L(r1 )and L(r2 ) are regular languages

We also know:
Regular languages are closed under:
Union Lr1  Lr2 
Concatenation Lr1  Lr2 
Star Lr1 *
Riphah International University FSD 46
Therefore:

Lr1  r2  Lr1  Lr2 

Are regular
Lr1 r2  Lr1  Lr2 
languages

Lr1 * Lr1 *

Riphah International University FSD 47

L((r1 )) is a regular language

Riphah International University FSD 48

 Proof – Part 2

2. For any regular language L there is

a regular expression r with L( r ) L

Proof by construction of regular expression

Riphah International University FSD 49

Since L is regular take the
NFA M that accepts it

L ( M ) L

Single final state

Riphah International University FSD 50
 From M construct the equivalent
Generalized Transition Graph
in which transition labels are regular
expressions

Example:
M
a c a c
a, b a b
Riphah International University FSD 51
 b b
Another Example:
a
q0 q1 a, b q2
b

b b
a
q0 q1 a  b q2
b
Riphah International University FSD 52
 b b
Reducing the states:
a
q0 q1 a  b q2
b

bb * a b

q0 bb * (a  b) q2
Riphah International University FSD 53
Resulting Regular Expression:

bb * a b

q0 bb * (a  b) q2

r (bb * a ) * bb * (a  b)b *

L ( r ) L ( M ) L
Riphah International University FSD 54
 In General
Removing states: g e
d c
qi q qj
a b
f
ae * d ce * b
g ce * d* d
 ce
qi qj
f
aeae
* b* b
Riphah International University FSD 55
The final transition
graph: r1 r4
r3
q0 qf
r2

The resulting regular expression:

r ( r1  r2 r4 * r3 ) * r2 r4 *
r r1 * r2 (r4  r3 r1 * r2 ) *
L ( r ) L ( M ) L
Riphah International University FSD 56