Properties of

Regular Languages

Costas Busch - LSU 1

For regular languages L1 and L2
we will prove that:
Union: L1  L2
Concatenation: L1L2
Star: L* Are regular
1
Languages
Reversal: LR
1

Complement: L1
Intersection: L1  L2
Costas Busch - LSU 2
We say Regular languages are closed under

Union: L1  L2
Concatenation: L1L2
*
Star: L1

Reversal: LR
1

Complement: L1
Intersection: L1  L2
Costas Busch - LSU 3
A useful transformation: use one accept state

NFA
a
b 2 accept states
a
b

Equivalent
a
NFA 1 accept state
a b

b 

Costas Busch - LSU 4
 In General
NFA

Equivalent NFA
 Single
 accepting

state
Costas Busch - LSU 5
 Extreme case

NFA without accepting state

Add an accepting state

without transitions

Costas Busch - LSU 6

 Take two languages

Regular language L1 Regular language L2

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

NFA M1 NFA M2

Single accepting state Single accepting state

Costas Busch - LSU 7

 Example

M1
n0
a
n
L1  {a b} b

M2
a
L2   ba b

Costas Busch - LSU 8

 Union
NFA for L1  L2
M1

 M2

w  L1  L2 w  L1 or w  L2
Costas Busch - LSU 9
 Example
n
NFA for L1  L2  {a b}  {ba}
n
L1  {a b}
a
b


 L2  {ba}
b a
Costas Busch - LSU 10
 Concatenation
NFA for L1L2
change to
regular state
M1 M2


w  L1 L2 w  w1w2 : w1  L1 and w2  L2

Costas Busch - LSU 11

 Example

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

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

Costas Busch - LSU 12

 Star Operation
NFA for L*
M
 change to
regular state
L( M )  L

w  w1w2  wk : wi  L
w L *
or w  
Costas Busch - LSU 13
 Example

*
NFA for L  {a b}
1
n *

n
L1  {a b}
a
 b


Costas Busch - LSU 14
 Reverse
R
NFA for L
M M

L( M )  L L( M )  LR

1. Reverse all transitions

2. Make the initial state accept state

and the accept state initial state
Costas Busch - LSU 15
 Example

M1
a
n
L1  {a b} b

M 1
a
L  {ba }
R
1
n
b

Costas Busch - LSU 16

 Complement

M M

L( M )  L L( M )  L

1. Take the DFA that accepts L

2. Make accept states regular

and vice-versa
Costas Busch - LSU 17
 Example
M1
a a, b

L1  {a b}
n b a, b

M 1
a a, b
L1  {a, b}  {a b}
* n

b a, b

Costas Busch - LSU 18

NFAs cannot be used for complement
Make accept states regular
and vice-versa

NFA M NFA M 

L( M )  {} L( M )  { }  L( M )

L( M )    {a, b}
* * it is not the
complement

Costas Busch - LSU 19

Same example with DFAs
Make accept states regular
and vice-versa
DFA M DFA M 
a, b a, b

L( M )  {} L( M )  {a, b}*  L( M )

L( M )    {a, b}
* * it is the
complement

Costas Busch - LSU 20

 Intersection

L1 regular
we show L1  L2
L2 regular regular

Costas Busch - LSU 21

DeMorgan’s Law: L1  L2  L1  L2

L1 , L2 regular, regular
L1 , L2 regular, regular
L1  L2 regular
L1  L2 regular
L1  L2 regular
Costas Busch - LSU 22
 Example

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

Costas Busch - LSU 23

 Another Proof for Intersection Closure

Machine M1 Machine M2
DFA for L1 DFA for L2

Construct a new DFA M that accepts L1  L2

M simulates in parallel M1 and M 2

Costas Busch - LSU 24
 States in M

qi , p j

State in M1 State in M2

Costas Busch - LSU 25

 DFA M1 DFA M2

q1 a q2 p1 a p2
transition transition

DFA M

q1, p1 a q2 , p2
New transition
Costas Busch - LSU 26
DFA M1 DFA M2

q0 p0
initial state initial state

DFA M

q0 , p0
New initial state
Costas Busch - LSU 27
 DFA M1 DFA M2

qi pj pk

accept state accept states

DFA M
qi , p j qi , pk

New accept states

Both constituents must be accepting states

Costas Busch - LSU 28
Example:

n0 m0
L1  {a b} n m
L2  {ab }
M1 M2
a b
q0 b q1 p0 a p1
a, b b a
q2 p2
a, b a, b
Costas Busch - LSU 29
DFA M for intersection

L( M )  {a nb}  {ab m }  {ab}

a, b

q0 , p0 a q0 , p1 b q1, p1 a q2 , p2

b a b a
q1, p2 b q0 , p2 q2 , p1

a b
a, b
Costas Busch - LSU 30
Construction procedure for intersection

1. Build Initial State

2. For each new state and for each symbol

add transition to either an existing state
or create a new state and point to it

3. Repeat step 2 until no new states

are added

4. Designate accept states

Costas Busch - LSU 31
Automaton for intersection

L  {a nb}  {ab m }  {ab}

q0 , p0

initial state

Costas Busch - LSU 32

Automaton for intersection

L  {a nb}  {ab m }  {ab}

q0 , p0 a q0 , p1
add transition and new state
M1 M2
for symbol a
q0 a q0 p0 a p1

q0 , p0 a q0 , p1

Costas Busch - LSU 33

Automaton for intersection

L  {a nb}  {ab m }  {ab}

q0 , p0 a q0 , p1

b M1 M2

q0 b q1 p0 b p2
q1, p2

add transition and new state M

for symbol b q0 , p0 b q1 , p2

Costas Busch - LSU 34

Automaton for intersection

L  {a nb}  {ab m }  {ab}

Repeat until no new states can be added a, b

q0 , p0 a q0 , p1 b q1, p1 a q2 , p2

b a b a
q1, p2 b q0 , p2 q2 , p1

a b
a, b

Costas Busch - LSU 35

Automaton for intersection

L  {a nb}  {ab m }  {ab}

q1 accept state for M 1
a, b
p1 accept state for M 2 add Accept state

q0 , p0 a q0 , p1 b q1, p1 a q2 , p2

b a b a
q1, p2 b q0 , p2 q2 , p1

a b
a, b

Costas Busch - LSU 36

Intersection DFA M:

simulates in parallel M1 and M 2

accepts string w if and only if:

M1 accepts string w
and M 2 accepts string w

L ( M )  L ( M1 )  L ( M 2 )
Costas Busch - LSU 37