Lecture Notes on Equivalent Languages and Simulations (COMP11212)

Equivalent Languages and Simulation

Simulations

Assumo two NFAs A = 1Q , g ., F, 5) and B (P , p ., E, Y) ↳ = he iff he a ha and he the
,



Definition We that relation simulation between automata A and B ↳ I he iff he n complement ((2) =
⑪
16 :
say a -
from Q to P is a




( (a) 0
*

if and only if ↳d La iff he n
- =




(E -4)
*

iff =
·
q ~p
. .

Lach Lan

·
if gup for some qeQ and peP then


ifa <q" then there exists pleP such that p
<p' and
q'up

qF implies pEE




=
Lxample
Al A B C D Give a simulation from A2 to A
a
b
, 2
> > > a ·

(2 A) ,



-f *
(y B) accepted by A2
a
·
, any words
will also be accepted by A1
·
(2 C) ,

#


Az X Y Z
a b
> 2 >
Give a simulation from Al to Az

There is no simulation
from As to A2




Further Examplo : DFA

Al A B D Simulation from As to A2 Simulation from A2 to A
b
T
a
(W , Al
a

(A w] start states start state
·
- 7 7 ·

,

*
I * A
& ·

(B x),
·
(X , B)
b

a ·

(C w),
·
(w c) ,




·
(D , Y)
·

(y D)
,

C
*


·
(D , 2)
·
(2 D)
,



B

Az w
# 2536
-



I A




b a b

-




...
W




2




Further Examplo : NFA
a



As a
*
Simulation from As to A2 Simulation from As to An
①
b
D
#
D ·
(A , A) Start state There is no simulation
A b B C
·

(B, Y)
·
(C 2)
,




Az ·
(A 2)
"
,




.... (C y)
·
D
,



N Y I




Conclusions
Two DFAs equivalent if simulation exists
are and only if a
·




Two NFAs equivalent if simulation exists. (it cannot exist they could still be equivalent )
·
are a and .