Równoważność DFA i NFA
Fakt. Każdy DFA jest NFA.
Twierdzenie. Niech L będzie językiem akceptowanym przez NFA.
Równoważność DFA, NFA i RE. Minimalny
Wtedy istnieje DFA akceptujący język L.
DFA
Dowód
Języki formalne i techniki translacji - Wykład 2
Niech NFA M = (Q, Ł, �, q0, F ).

Definiujemy DFA M = (Q , Ł, � , q0, F ) symulujący równolegle
wszystkie przejścia przez automat M.
Maciek Gębala
Q = 2Q śledzimy wszystkie podzbiory stanów M

F ą" Q q " F �!�! "p"q p " F
27 lutego 2013

q0 = {q0}

� (q, a) = �(p, a)
p"q
Dowód indukcyjny po długości wczytywanego słowa.
Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA
Przykład Równoważność NFA i NFA�
NFA
Fakt. Każdy NFA jest NFA�.
M = ({q0, q1}, {0, 1}, �, q0, {q1})
Twierdzenie. Jeśli L jest językiem akceptowanym przez NFA� to jest
� 0 1
również akceptowany przez NFA.
q0 {q0, q1} {q1}
q1 " {q0, q1}
Dowód
Niech NFA� M = (Q, Ł, �, q0, F ).
Równoważny DFA

Definiujemy NFA M = (Q, Ł, � , q0, F )

M = ({{q0}, {q1}, {q0, q1}, "}, {0, 1}, � , {q0}, {{q1}, {q0, q1}})
F *" {q0} jeśli z q0 można dojść do q " F �-przejściami

F =
F w przeciwnym przypadku
� 0 1

{q0} {q0, q1} {q1}
Ć
� (q, a) = �(q, x)
{q1} " {q0, q1}
x"(�"a�")
{q0, q1} {q0, q1} {q0, q1}
M nie ma �-przejść. Dowód indukcyjny po długości słowa.
" " "
Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA
Równoważność DFA i RE Równoważność DFA i RE
Twierdzenie. Jeżeli L jest akceptowany przez DFA, to L jest
reprezentowany przez wyrażenie regularne.
Dowód
Twierdzenie. Niech r będzie wyrażeniem regularnym opisującym
język L. Wtedy istnieje NFA� który akceptuje L.
Niech L będzie akceptowany przez DFA
M = ({q1, . . . , qn}, Ł, �, q1, F ).
Zdefiniujmy
Dowód
Indukcja po budowie wyrażenia regularnego. k
Ć Ć
Rij = {x " Ł" : �(qi, x) = qj'""y=prefix(x),y=�,y=x�(qi, y) = ql =�! l k}

k
Rij  zbiór wszystkich słów z jakimi można przejść ze stanu qi do
Dowód na tablicy.
stanu qj używając po drodze tylko pierwszych k stanów (i,j mogą być
n
większe od k). Rij - wszystkie łańcuchy z którymi możemy przejść z
qi do qj.

n
L = R1j
qj "F
Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA
Równoważność DFA i RE Minimalny DFA
Dowód cd.
Definicja rekurencyjna
Dla każdego języka regularnego istnieje dokładnie jeden

(dokładnością do izomorfizmów) DFA o minimalnej liczbie stanów.
{a : �(qi, a) = qj} i = j

0
Rij =
(Własność ta wynika z twierdzenia Myhill-Nerode, które jednak
{a : �(qi, a) = qi} *" {�} i = j
zostanie pominięte na wykładzie.)
k k k-1 k k-1
Rij = Rik-1(Rkk )"Rkj-1 *" Rij k > 0
Idea algorytmu
k k
A
atwo skonstruować wyrażenie regularne rij opisujące Rij .
Chcemy znalez
ć takie stany które można ze sobą połączyć (stany
Dowód poprawności przez indukcję po k.
równoważne). Dwa stany równoważne to takie, że dla każdego x
startując z tych stanów albo znajdziemy się równocześnie w stanach
Przykład
akceptujących albo nieakceptujących.
Na ćwiczeniach.
Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA
Algorytm minimalizacji Przykład
Oznaczamy pary stanów, które nie są równoważne.
1
p " F '" q " Q \ F oznacz parę (p, q)
M = ({a, b, c, d, e, f }, {0, 1}, �, a, {c, d, e})
2
p, q " (F � F ) *" (Q \ F � Q \ F ) t.że p = q

� 0 1
"a"Ł t.że (�(p, a), �(q, a)) jest oznaczona
a b c
oznacz (p, q)
b a d
oznacz w sposób rekurencyjny wszystkie nieoznaczone
c e f
pary na liście (p, q)
d e f
/* żadna para (�(p, a), �(q, a)) nie jest oznaczona */
e e f
a " Ł
f f f
umieść parę (p, q) na liście (�(p, a), �(q, a)),
o ile �(p, a) = �(q, a)

DFA uzyskany przez złączenie stanów równoważnych uzyskanych
Wykonanie algorytmu na tablicy.
przez powyższy algorytm, z usuniętymi stanami nieosiągalnymi, jest
minimalnym DFA dla danego języka.
Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA
Przykład cd.
DFA po minimalizacji
M = ({ab, cde, f }, {0, 1}, �, ab, {cde})
� 0 1
ab ab cde
cde cde f
f f f
Maciek Gębala Równoważność DFA, NFA i RE. Minimalny DFA