Uniwersytet Zielonogórski

Instytut Sterowania i Systemów Informatycznych

Teoretyczne Podstawy Informatyki

Lista 4 – Deterministyczne i niedeterministyczne automaty

1

Wprowadzenie

Automat skończony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach. System ta-
ki może się znajdować w jednym ze skończonej liczby stanów (dopuszczalne są także systemu gdzie automat
może się znajdować w wielu stanach na raz). Stan systemu stanowi podsumowanie informacji dotyczących po-
przednich wejść. Informacja ta jest niezbędna aby do określenia zachowania systemu przy następnych wejściach.
Istnieje wiele przykładów zastosowań automatów. Prostym przykładem jest mechanizm windy. Mechanizm ten
nie pamięta wszystkich poprzednich żądań. Pamiętane jest tylko bieżące piętro, kierunek ruchu (w górę lub w
dół) oraz zbiór żądań do obsłużenia.

Innymi przykładami stanowią powszechnie używane programy, takie jak edytory tekstów i analizatory lek-

sykalne spotykane w większości kompilatorów. Są one bardzo często projektowane jako systemy skończenie
stanowe. Analizator leksykalny przegląda symbole programu komputerowego w celu zlokalizowania łańcuchów
symboli odpowiadających identyfikatorom, stałym numerycznym, słowom kluczowym oraz innymi jednostkom
leksykalnym. W trakcie tego procesu analizator leksykalny pamięta tylko skończoną ilość informacji, takich jak
np.: jak długi przedrostek słowa kluczowego był widziany chwili startu. Teoria automatów skończonych ma
bardzo duży udział w projektowaniu efektywnych analizatorów łańcuchów.

Przykład analizy, gdzie znajduje zastosowanie opis przy pomocy automatu skończonego może zostać za-

prezentowany na przykładzie następującego problemu: na brzegu rzeki stoi człowiek z wilkiem, kozą i sałatą.
Zadaniem jest przedostanie się na drugą stronę rzeki. Utrudnieniem są pewne warunki, człowiek może przepły-
nąć rzekę tylko z jednym pasażerem, czyli albo z wilkiem, albo z kozą bądź z sałatą. Jeśli jednak zostawi on
wilka i kozę bez nadzoru na którymkolwiek brzegu, to wilk pożre kozą. Jeśli koza i sałata zostaną bez opieki,
to koza pożre sałatę.

C W K S - #

s t a r t

W S - C K

C W S - K

S - C W K

W - C K S

C K S - W

C W K - S

K - C W S

C K - W S

# - C W K S

K

C

W

S

K

K

S

W

C

K

Rysunek 1: Diagram przejść do problemu człowieka, wilka kozy oraz sałaty

Właściwe rozwiązanie zostanie odnalezione, gdy zauważymy, że istotną informacją jest to, jakie obiekty

znajdują się na każdym z brzegów po dowolnej stronie rzeki. Można wskazać, że istnieje szesnaście podzbiorów
złożonego z człowieka (C), wilka (W), kozy (K) oraz sałaty (S). Zakładamy, że stan odpowiada podzbiorowi,
który opisuje co znajdującemu się na lewym i prawym brzegu. Do zwiększenia czytelności będzie stosować kreskę
do rozdzielenia obiektów znajdujących się na lewym oraz prawym brzegu. Przykład stanu W S − CK oznacza,
że wilka i sałata znajdują się na lewym a na prawym brzegu jest człowiek i koza.

Wejścia systemu to działania podejmowane przez człowieka. Człowiek może się przeprawiać sam, z wilkiem,

z kozą i naturalnie z sałatą. Stanem początkowym jest CW KS − # a końcowym # − CW KS (gdzie symbol #
oznacza iż dany brzeg jest pusty). Diagram przejść który pokazuje sposób rozwiązania przedstawia rysunek

1

.

Litery na łukami oznaczają pasażera który został przewieziony przez człowieka.

1

1.1

Definicja deterministycznego automatu skończonego

Deterministyczny automat skończony (w skrócie DAS lub ang. FDA – finite deterministic automata) jest zbu-
dowany z następujących elementów:

1. skończonego zbioru stanów, oznaczonych symbolem Q

2. skończonego zbioru symboli wejściowych (nazywanego także alfabetem), oznaczonych symbolem Σ

3. funkcji przejścia, przyjmującej za argument stan oraz symbol wejściowy a jej wynikiem jest stan, funkcja

przejścia będzie oznaczana przez symbol δ

4. stanu początkowego, jest to jeden wyróżniony stan z Q

5. zbioru stanów końcowych lub akceptujących F , gdzie F ⊂ Q

W skrócie o pewnym określonym DAS można mówić jako o następującej krotce o pięciu elementach:

A = (Q, Σ, δ, q

0

, F )

(1)

gdzie A reprezentuje nazwę automatu, Q - to zbiór stanów, Σ - zbiór symboli wejściowych, δ - funkcja przejścia,
q

0

- stan początkowy, natomiast przez F oznaczamy zbiór stanów akceptujących.

Funkcja przejścia jest określona w następujący sposób: jeśli q jest stanem, natomiast a pewnym symbolem

wejściowym, to wartością funkcji δ(q, a) jest stan p, co oznacza że ze stanu q można przejść do stanu p jeśli
pojawił się symbol a.

Graficzną reprezentacją automatu jest diagram przejść. Dla deterministycznego automatu skończonego

A = (Q, Σ, δ, q

0

, F ), diagram przejść to graf skierowany zbudowany następująco:

a) każdemu stanowi ze zbioru Q odpowiada wierzchołek,

b) dla pewnego stanu q ∈ Q i dla symbolu wejściowego a ∈ Σ funkcja δ(q, a) = p. W diagramie przejść taka

sytuacja oznacza iż istnieje łuk z wierzchołka q do wierzchołka p (jeśli istnieje wiele symboli alfabetu Σ
powodujących przejście z q do p, to diagram przejść dla czytelności zawiera tylko jeden łuk etykietowany
listą symboli),

c) stan początkowy q

0

jest wskazywany przez strzałkę z napisem start (strzałka ta nie wychodzi z żadnego

wierzchołka),

d) wierzchołki odpowiadające stanom akceptującym (należą do zbioru F ) oznaczane są podwójnym okręgiem,

natomiast stany nienależące do F są oznaczane pojedynczym okręgiem.

Wygodnym sposobem reprezentacji funkcji przejścia δ jest tablica przejść. Jest to tablicowa reprezentacja

funkcji δ, przyjmującej dwa argumenty i zwracającej jakąś wartość. Wiersze tablicy odpowiadają stanom, na-
tomiast kolumny wejściom. Wpis w wierszu odpowiadającym stanowi q i kolumnie odpowiadającej wejściu a to
zapis stanu δ(q, a).

1.1.1

Przykład dla ciągów x01y

Załóżmy chcemy zbudować automat deterministyczny który będzie zdolny do weryfikacji czy podany ciąg znaków
spełnia definicję C (inaczej mówiąc przez C rozumiemy pewien język) o następującej postaci:

C = {w | w jest postaci x01y dla pewnych łańcuchów x, y złożonych wyłącznie z zer i jedynek}

(2)

Inną, ale naturalnie równoważną definicją jest

C = {x01y | x, ysą dowolnymi łańcuchami zer i jedynek}

(3)

Przykłady łańcuchów należących do języka C są ciągi: 01, 11010 oraz 100011. Przykładami ciągów nienależących
do języka C są ciągi ε (czyli ciąg pusty), 0, 111000. Łatwo stwierdzić iż alfabet to tylko dwa znaki Σ = {0, 1}.
Istnieje pewien zbiór stanów Q którego na razie nie precyzujemy ale już można wyróżnić stan początkowy q

0

.

Automat musi zostać w taki sposób skonstruowany aby niejako pamiętał ważne fakty odnoście co pojawiło się
na wejściu. W przypadku postawionego zadania możemy wyróżnić trzy następujące zdarzenia:

2

0

1

→ q

0

q

2

q

0

?q

1

q

1

q

1

q

2

q

2

q

1

Tabela 1: Tablica przejść dla automatu z rysunku (

2

)

1. Czy na wejściu pojawił się podciąg 01? Jeśli tak, to można zaakceptować dowolny ciąg zer i jedynek,

ponieważ ciąg jest zbudowany zgodnie z językiem L. Oznacza to także że następne stany mogą być
stanami akceptującymi.

2. Jak dotąd podciąg 01 nie pojawił się jeszcze, ale ostatnim widzianym symbolem było 0, jeśli teraz pojawi

się 1, oznaczać to będzie, że pojawił się podciąg 01 i następne symbole mogą być dowolnym ciągiem zer i
jedynek.

3. Jak dotąd podciąg 01 nie pojawił się jeszcze, co więcej poprzedni symbol nie został jeszcze podany,

bo automat właśnie rozpoczął swoją pracę bądź ostatnim symbolem była jedynka. W takim przypadku
automat A nie może zaakceptować słowa, dopóki nie pojawi się zero, a bezpośrednio po zerze jedynka.

Wymienione warunki należy przedstawić za pomocą stanów. Warunek (3) będzie reprezentowany przez stan

q

0

. Jest to tym uzasadnione, że jeśli zaczynamy, to musimy wykryć zero, a potem jedynkę. Jeśli będąc w stanie

q

0

zobaczymy w pierwszej kolejności jedynkę, to naturalnie nadal musimy pozostać w stanie q

0

. Zapiszemy to

w następujący sposób δ(q

0

, 1) = q

0

.

Będąc w stanie q

0

, gdy napotkamy zero to zaczyna obowiązywać warunek (2), czyli δ(q

0

, 0) = q

2

. Przybliża

nas to wykrycia, obecności podciągu 01. Pierwsza sytuacja jak jest istotna w stanie q

2

to wykrycie następującego

symbolu którym jest zero. Jeśli, tak jest to, δ(q

2

, 0) = q

2

, co oznacza iż naturalnie pozostajemy w stanie q

2

.

Jednakże jeśli będąc w stanie q

2

, jeśli wykryjemy zero to wiedząc iż pojawiło się już zero to uzyskaliśmy

informację o tym, że wystąpił pod ciąg 01. Przechodzimy do stanu q

1

, oznaczający stan akceptujący, δ(q

2

, 1) =

q

1

.

Stan q

1

może przyjmować, zero bądź jedynkę w dowolnej kolejności ponieważ już wcześniej udało się nam

stwierdzić obecność 01. Funkcja przejścia posiada postać δ(q

1

, 0) = q

1

oraz δ(q

1

, 1) = q

1

.

Zbierając uzyskane informacje, formalnie automat A zdefiniujemy w następujący sposób:

A

DAS

= ({q

0

, q

1

, q

2

}, {0, 1}, δ, q

0

, {q

1

})

(4)

Określanie automatu w sposób formalny ze szczegółowym oraz obszernym słownym opisem funkcji przejścia

jest żmudne, zabiera sporo czasu oraz co najważniejsze jest mało czytelne choć naturalnie zrozumiałe. Warto
jednak stosować dwa inne podejścia w przypadku opisu postaci funkcji przejścia. Diagram przejść dla opisanego
automatu prezentuje rysunek (

2

) natomiast tablica przejść funkcji δ to tabela (

1

).

q 0

q 2

s t a r t

1

0

0

q 1

1

0 , 1

Rysunek 2: Schemat deterministycznego automatu akceptującego wszystkie takie ciągi zbudowane z zer oraz
jedynek, które zwierają podciąg 01

1.2

Rozszerzona funkcja przejścia

Rozszerzona funkcja przejścia opisuje sytuację, gdy deterministyczny automat skończony rozpoczyna pracę
w dowolnym stanie. Funkcję taką definiuje się wykorzystując standardową funkcję przejścia δ. Rozszerzona
funkcja przejścia ˆ

δ to funkcja, która otrzymuje stan q i łańcuch w, a jej wynikiem jest stan p, jaki osiągnie

3

automat, zaczynając działanie w stanie q i przetwarzając dostarczony ciąg w. Funkcja ˆ

δ posiada indukcyjną

definicję po długości łańcucha wejściowego:
Podstawa: ˆ

δ(q, ε) = q, jeśli automat znajduje się w stanie q i nie został odczytany żaden symbol wejściowy, to

automat nadal znajduje się w stanie q.
Krok Indukcyjny: Zakładamy, że w jest łańcuchem o postaci xa, co oznacza iż symbol a jest ostatnim
symbolem w, a x jest łańcuchem składającym się ze wszystkich symboli w poza ostatnim. Czyli, słowo w = 1101
zostałoby rozbite na x = 110 oraz a = 1. Taka definicja pozwala na stwierdzenie iż

ˆ

δ(q, w) = δ(ˆ

δ(q, x), a).

Wyjaśnienie powyższego zapisu jest następujące. Aby obliczyć ˆ

δ(q, w), obliczamy ˆ

δ(q, x), czyli stan, w którym

znajdzie się automat po przetworzeniu wszystkich symboli w poza ostatnim. Jeśli założymy, że tym stanem jest
p, czyli ˆ

δ(q, x) = p. Toteż, dokonując przejścia ze stanu p na wejściu a, w przypadku ostatniego symbolu w,

otrzymamy ˆ

δ(q, w), czyli ostatecznie otrzymamy ˆ

δ(q, w) = δ(p, a). 

1.2.1

Język o parzystej liczbie zer i jedynek

Przykładem ilustrującym zastosowania rozszerzonej funkcji przejścia będzie skończony automat deterministycz-
ny, rozpoznający czy podany wyraz należy do języka o parzystej liczbie zer i jedynek. O takim automacie można
powiedzieć iż będzie zliczał wystąpienia zer bądź jedynek modulo 2. Stan będzie używany do pamiętania, czy
widziana dotąd liczba zer bądź jedynek jest parzysta bądź nieparzysta. Można wyróżnić cztery stany, a ich opis
przedstawia się następująco:

q

0

: ujrzana dotąd liczba jedynek oraz zer jest parzysta,

q

1

: ujrzana liczb zer jest parzysta, ale liczb jedynek jest nieparzysta,

q

2

: ujrzana liczb jedynek jest parzysta, ale liczb zero jest nieparzysta,

q

3

: ujrzana dotąd liczba jedynek oraz zer jest nieparzysta.

Z opisu wynika, że stan q

0

jest stanem początkowym oraz końcowym. Diagram przejść jest przedstawiony na

rysunku

3

. Tabela przejść przyjmuje następującą postać:

0

1

→ q

0

q

2

q

1

?q

1

q

3

q

0

q

2

q

0

q

3

q

3

q

1

q

2

Funkcja ˆ

δ nadaje się bardzo dobrze do ilustracji działania, bądź też sprawdzenia czy automat został dobrze

zaprojektowany np.: chcemy sprawdzić czy ˆ

δ(q

0

, 110101) = q

0

. Sposób obliczanie wartości funkcji ˆ

δ(q

0

, w) polega

na obliczanie wartości dla każdego prefiksu w, poczynając od ε i idąc w kierunku rosnącej długości, przedstawia
się to następująco:

• ˆ

δ(q

0

, ε) = q

0

,

• ˆ

δ(q

0

, 1) = δ(ˆ

δ(q

0

, ε), 1) = δ(q

0

, 1) = q

1

,

• ˆ

δ(q

0

, 11) = δ(ˆ

δ(q

0

, 1), 1) = δ(q

1

, 1) = q

0

,

• ˆ

δ(q

0

, 110) = δ(ˆ

δ(q

0

, 11), 0) = δ(q

0

, 0) = q

2

,

• ˆ

δ(q

0

, 1101) = δ(ˆ

δ(q

0

, 110), 1) = δ(q

2

, 1) = q

3

,

• ˆ

δ(q

0

, 11010) = δ(ˆ

δ(q

0

, 1101), 0) = δ(q

3

, 0) = q

1

,

• ˆ

δ(q

0

, 110101) = δ(ˆ

δ(q

0

, 11010), 1) = δ(q

1

, 1) = q

0

.

4

q 0

q 1

q 3

q 2

s t a r t

1

1

1

1

0

0

0

0

Rysunek 3: Deterministyczny automat skończony akceptujący wyrazy zbudowane z parzystej liczby zer oraz
jedynek

1.3

Niedeterministyczny automat skończony

Niedeterministyczny automat skończony jest zbudowany w dość podobny sposób jak automat deterministyczny,
posiada skończony zbiór symboli wejściowych, jeden stan początkowy oraz zbiór stanów akceptujących. Istnieje
także funkcja ˆ

δ jednak to ona stanowi o zasadniczej różnicy pomiędzy automatami. Funkcja ˆ

δ podobnie jak w

przypadku automaty deterministyczne za argumenty przyjmuje stan oraz symbol wejściowy jednak w wyniki
może wygenerować zbiór stanów. Co oznacza iż automat niedeterministyczny może znajdować się w kilku stanach
naraz.

Formalna definicja niedeterministyczne automatu skończonego to następująca piątka (identyczna jak w przy-

padku automatu deterministycznego):

A = (Q, Σ, δ, q

0

, F )

(5)

gdzie

1. Q jest skończonym zbiorem stanów,

2. Σ jest skończonym zbiorem symboli wejściowych,

3. q

0

∈ Q to stan początkowy,

4. F ⊆ Q – jest zbiorem stanów końcowych lub akceptujących,

5. δ jest funkcją przejścia, która przyjmuje jako argumenty stan z Q i symbol wejściowy Σ i zwraca podzbiór

Q.

Rysunek

4

przedstawia niedeterministyczny automat akceptujący łańcuchy zero-jedynkowe, które na końcu

zawierają ciąg 01. Stan początkowy to stan q

0

. Automat pozostaje w tym stanie, gdy jeszcze nie „zgadł”, iż

rozpoczął się końcowy łańcuch 01. Bowiem, zawsze jest możliwe, iż następny symbol nie rozpoczyna końcowego
01, nawet gdy tym końcowym symbolem jest 0.

Jeśli jednak następnym symbolem jest końcowe 0, to automat zgaduje, że końcowe 01 się rozpoczęło. Zatem

łuk o etykiecie 0, kieruje nas do stanu q

0

ale drugi z łuków przenosi nas do stanu q

1

. Inaczej mówiąc automat

znajduje się w tych dwóch stanach. Będąc jednak w stanie q

1

, jeśli automat zobaczy 1 to przechodzi do stanu

q

2

i łańcuch zostanie zaakceptowany.

q 0

q 1

s t a r t

0

0 , 1

q 2

1

Rysunek 4: Niedeterministyczny automat skończony akceptujący wyrazy kończące się wyrażeniem 01

5

Rysunek

5

przedstawia jeden ze sposób jakie automat z rysunku przechodzi przez poszczególne stany dla

ciągu wejściowego 00101. Automat rozpoczyna działanie będąc w stanie q

0

. Po odczytaniu pierwszego symbolu,

czyli zera może przejść do stanu q

0

lub q

1

. Zgodnie z założeniem automat przechodzi do obydwu stanów.

Następnie automat odczytuje kolejne zero. Ze stan q

0

możemy przejść do stanów q

0

albo q

1

. Jednak stan q

1

nie przejścia dla zera, więc ten wątek przetwarzania niejako zamiera i może zostać przez automat porzucony. Po
odczytaniu trzeciego symbolu 1, należy wziąć pod uwagę przejścia z q

0

jak i q

1

. Stwierdzić można iż za pomocą

symbolu 0 stan q

0

przechodzi na q

0

, podczas gdy q

1

przechodzi tylko na q

2

. Po odczytaniu 001 automat znajduje

się w dwóch stanach q

0

oraz q

2

. Ponieważ q

2

jest stanem akceptującym to automat zaakceptuje wejście 001.

q 0

q 0

q 1

q 0

q 0

q 1

q 2

q 0

q 1

q 0

q 2

0

0

1

0

1

b r a k r u c h u

b r a k r u c h u

Rysunek 5: Stan, przez jakie może przejść niedeterministyczny automat skończony podczas przetwarzania słowa
wejściowego 00101

Wejściowy łańcuch znaków jeszcze się nie skończył. Kolejny symbol 0 powoduje zatrzymanie się wątku q

2

,

ale ze stanu q

0

można przejść do dwóch kolejnych stanów q

0

oraz q

1

. Ostatni symbol 1, powoduje przejście z

q

0

do q

0

oraz q

1

do q

2

. Ponieważ ponownie został osiągnięty stan akceptujący, toteż oznacza to iż ciąg 00101

został zaakceptowany.

Na podstawie tego przykładu już łatwo podać tabelę dla funkcji przejścia, jednak tym razem wartościami

są zbiory, jeśli z którego stanu nie ma przejścia przy pomocy symbolu zbioru pustego

0

1

→ q

0

{q

0

, q

1

}

{q

0

}

q

1

∅

{q

2

}

?q

2

∅

∅

1.3.1

Rozszerzona postać funkcji przejścia

W dość podobny sposób jak dla automatów deterministycznych można rozszerzyć funkcję δ automatu niedeter-
ministycznego do funkcji ˆ

δ. Indukcyjna definicja ˆ

δ jest również podobna:

Podstawa: ˆ

δ(q, ε) = q

0

– czyli, nie zostały odczytane jeszcze żadne symbole, więc stan pozostaje bez zmian.

Krok indukcyjny: Jeśli założymy, że w = xa, gdzie a jest końcowym symbolem w, natomiast x resztą słowa
w, oraz ˆ

δ(q, x) = {p

1

, p

2

, . . . , p

n

} to:

k

[

i=1

δ(p

i

, a) = {r

1

, r

2

, . . . , r

m

}

(6)

Wtedy ˆ

δ(q, w) = {r

1

, r

2

, . . . , r

n

}. Można powiedzieć, że wartość funkcji ˆ

δ(q, w) została obliczona poprzez wy-

znaczenie ˆ

δ(q, x), a następnie prześledzenie dowolnego przejścia opatrzonego etykietą a.

Dla wejścia 00101 i automatu przedstawionego na rysunku

4

rozszerzona postać funkcji przejścia jest nastę-

pująca:

1. ˆ

δ(q

0

, ε) = {q

0

} ,

2. ˆ

δ(q

0

, 0) = δ(q

0

, 0) = {q

0

, q

1

} ,

3. ˆ

δ(q

0

, 00) = δ(q

0

, 0) ∪ δ(q

1

, 0) = {q

0

, q

1

} ∪ ∅ = {q

0

, q

1

} ,

4. ˆ

δ(q

0

, 001) = δ(q

0

, 1) ∪ δ(q

1

, 1) = {q

0

} ∪ {q

2

} = {q

0

, q

2

} ,

5. ˆ

δ(q

0

, 0010) = δ(q

0

, 0) ∪ δ(q

2

, 0) = {q

0

, q

1

} ∪ ∅ = {q

0

, q

1

} ,

6. ˆ

δ(q

0

, 00101) = δ(q

0

, 1) ∪ δ(q

1

, 1) = {q

0

} ∪ {q

2

} = {q

0

, q

2

} .

6

1.4

Automaty niedeterministyczne z pustymi przejściami

Własnością automatów niedeterministycznych jest możliwość przechodzenia do wielu stanów równocześnie. Jed-
nak zawsze przejścia są dokonywane przy pomocy określonego symbolu. Dalszym „poluzowaniem” reguł jest
dopuszczenie do sytuacji, gdy przejścia następują spontaniczne. Automat może przejść do innego stanu bez
otrzymania symbolu wejściowego (symbol pusty jest oznaczany jako ε). Ta nowa właściwość nie zwiększa mocy
obliczeniowej automatów skończonych.

Rysunek

6

przedstawia automat z ε-przejściami który akceptuje liczby dziesiętne zawierające następujące

znaki:

1. opcjonalny znak plus lub minus,

2. pierwszy łańcuch cyfr,

3. kropkę dziesiętną,

4. drugi łańcuch cyfr.

Pierwszy łańcuch cyfr może być pusty, ale co najmniej jeden z tych dwóch łańcuchów cyfr musi być niepusty.

Automat posiada kilka interesujących przejść. Pierwszym jest przejście ze stanu q

0

do stanu q

1

przy pomocy

ε, +, −. Stan q

1

przedstawia sytuację, w której automat mógł zobaczyć znak liczby, jeśli taki wystąpił i pewne

cyfry, ale nie kropkę dziesiętną. Wykryciem kropki dziesiętnej zajmuje się stan q

2

, przejście do tego stanu

oznacza iż widziana była kropka i jakieś poprzedzające ją cyfry. Nieco inne znaczenie posiada stan q

4

. Będąc w

tym stanie, wiadomo iż była widziana przynajmniej jedna cyfra. Stan q

3

określa się znacznie więcej. Ten stan

oznacza, że były widziane cyfry (na pewno jedna), po niej kropka dziesiętna i również przynajmniej jedna cyfra
po kropce. Pozostanie w tym stanie oznacza odczytanie pozostałych cyfr lub przejścia do stanu końcowego, co
oznacza akceptację ciągu znaków.

q 2

s t a r t

q 1

q 3

q 4

q 5

e , + , -

c y f r a

c y f r a

e

c y f r a

c y f r a

.

.

q 0

Rysunek 6: Niedeterministyczny automat z przejściami ε (oznaczono wyjątkowo przez małą literę „e”) akcep-
tujący liczby dziesiętne

Formalnie definicja automatu przejściami typu ε, przedstawia się identycznie jak poprzednia dwa typy au-

tomatów, A = {Q, Σ, δ, q

0

, F }. Wszystkie składowe mają taką same znaczenia ale dla funkcji przejścia δ mamy

następujące argumenty:

1. stan z Q

2. element zbioru Σ∪{ε}, może to być symbol wejściowy bądź symbol ε. Wymagane jest aby symbol łańcucha

pustergo ε nie należał do alfabetu Σ (unikamy w ten sposób nieporozumień).

Automat przedstawiony na rysunku

6

formalnie jest określony w następujący sposób:

E = ({q

0

, q

1

, . . . , q

s

}, {., +, −, 0, 1, . . . , 9}, δ, {q

5

})

Funkcja przejścia δ jest określona przez następującą tabelę:

ε

+, −

.

0, 1, . . . , 9

q

0

{q

1

}

{q

1

}

∅

∅

q

1

∅

∅

{q

2

}

{q

1

, q

4

}

q

2

∅

∅

∅

{q

3

}

q

3

{q

5

}

∅

∅

{q

3

}

q

4

∅

∅

{q

3

}

∅

q

5

∅

∅

∅

∅

7

1.4.1

Domknięcie stanu typu ε

Pojęcie ε-domknięcia jest bardzo istotne w dalszych rozważaniach. Pojęcie to w sposób nieformalny można wpro-
wadzić w następujący sposób: ε-domknięcie stanu q to stany które są osiągane tylko i wyłącznie po wszystkich
przejściach ze stanu q opatrzonych etykietą ε. Inne stany osiągnięte ze stanu q także podlegają tej procedurze,
należy przejść do wszystkich ε-przejściach.

Formalnie ε-domknięcie ED(q) jest definiowane w następujący sposób:

Podstawa: Stan q należy do ED(q).
Krok indukcyjny: Jeśli stan p należy do ED(q) oraz istnieje przejście ze stanu p do stanu r o etykiecie ε, to
r też należy do ED(q). Co więcej, dla funkcji przejścia δ i stanu p ∈ ED(q) to ED(q) zawiera także wszystkie
stany z δ(p, ε).

Dla automatu przedstawionego na rysunku

6

każdy stan jest własnym ε-domknięciem oraz dla dwóch stanów

mamy: ED(q

0

) = {q

0

, q

1

} oraz ED(q

3

) = {q

3

, q

5

}

Inny przykład, to automat o następującym diagramie:

1

2

3

6

2

3

7

e

e

e

e t y 2

e t y 1

e

e

Rysunek 7:

Dla stanu 1 stosując definicję indukcyjną otrzymamy:

ED(1) = {1, 2, 3, 4, 6}

1.4.2

Rozszerzona funkcja przejścia

Niech E = {Q, Σ, δ, q

0

, F } będzie niedeterministycznym automatem z przejściami ε. Funkcja ˆ

δ jest rozszerzoną

funkcją przejścia, czyli ˆ

δ(q, w) to zbiór stanów osiągalnych po ścieżce, której etykiety tworzą słowo w. Rekuren-

cyjna definicja ˆ

δ jest określona w następujący sposób:

Podstawa: Wartość rozszerzonej funkcji przejścia jest równa domknięciu, jeśli badaną etykietą dla stanu q jest
ε: ˆ

δ(q, ε) = ED(q).

Krok indukcyjny: Zakładamy, że w = xa, gdzie a jest ostatnim symbolem w. Ponieważ a należy do Σ to z
definicji nie może ono być równe ε. Wartość ˆ

δ(q, w) może zostać obliczona na trzy sposoby:

1. Niech ˆ

δ(q, x) = {p

1

, p

2

, . . . , p

k

}. Stany p

i

odzwierciedlają drogę po których możemy dość ze stanu q do

stanu x. Ścieżka ta może zawierać ε-przejścia, może również kończyć się takim przejściem.

2. Niech

S

k
i=1

δ(p

i

, a) = {r

1

, r

2

, . . . , p

m

}. Ten przypadek opisuje drogę, gdzie idziemy po wszystkich przej-

ściach o etykiecie a ze stanów, do których możemy dojść z q po ścieżkach o etykiecie x. Stany r

j

to

niektóre ze stanów, osiągalne z q po ścieżkach o etykiecie w. Dodatkowe stany, do których możemy dojść,
znajdujemy, wychodząc z r

j

i idąc krawędziami etykietowanymi przez ε. Te drogi są opisane w następnym

punkcie:

3. Postać funkcji ˆ

δ(q, w) =

S

m
j=1

ED(r

j

) obejmuje domknięcia wszystkich ścieżek z q o etykiecie w. Bo-

wiem, rozważane są możliwości istnienia dodatkowych krawędzi o etykiecie ε, które można wykorzystać
po dokonaniu przejść na ostatnim symbolu a należącym do Σ.

Wykorzystując diagram automatu

6

obliczenia wartości ˆ

δ(q

0

, 5.6) przedstawiają się następująco:

• ˆ

δ(q

0

, ε) = ED(q

0

) = {q

0

, q

1

}

8

• Dla ˆ

δ(q

0

, 5) obliczenia są następujące:

1. W pierwszej kolejności należy obliczyć przejścia na wejściu 5 ze stanów q

0

i q

1

, które otrzymano po

obliczeniu ˆ

δ(q

0

, ε):

δ(q

0

, 5) ∪ δ(q

1

, 5) = ∅ ∪ {q

1

, q

4

} = {q

1

, q

4

}

2. Następnie trzeba wyznaczyć ε-domknięcia w kroku (1). Otrzymamy:

ED(q

1

) ∪ ED(q

4

) = {q

1

} ∪ {q

4

} = {q

1

, q

4

}

Otrzymaliśmy taki sam zbiór jak dla funkcji ˆ

δ(q

0

, 5).

• Obliczenia dla ˆ

δ(q

0

, 5.) przy wykorzystaniu zbioru wyznaczonego w poprzednim punkcie:

1. δ(q

1

, .) ∪ δ(q

4

, .) = {q

2

} ∪ {q

3

} = {q

2

, q

3

}

2. ˆ

δ(q

0

, 5.) = ED(q

2

) ∪ ED(q

3

) = {q

2

} ∪ {q

3

, q

5

} = {q

2

, q

3

, q

5

}

• Obliczenia dla ˆ

δ(q

0

, 5.6):

1. δ(q

2

, 6) ∪ δ(q

3

, 6) ∪ δ(q

5

, 6) = {q

3

} ∪ {q

3

} ∪ ∅ = {q

3

}

2. ˆ

δ(q

0

, 5.6) = ED(q

3

) = {q

3

, q

5

}

Ponieważ wartość dla ˆ

δ(q

0

, 5.6) zawiera stan akceptujacy q

5

, więc łańcuch 5.6 należy do języka automatu z

rysunku

6

.

Pozwala to na ogólne zdefiniowanie języka dla automatu niedeterministycznego, niech E = {Q, Σ, δ, q

0

, F }

to podobnie jak w pozostałych dwóch typach automatów L(E) = {w | ˆ

δ(q

0

, w) ∩ F 6= ∅}. Język automatu E to

zbiór takich słów w przeprowadzających stan początkowy na co najmniej jeden stan akceptujący.

2

Własności automatów

Automat skończony A jest zupełny (znakiem # wyjątkowo oznaczamy moc zbioru), gdy:

∀

a∈Σ

∀

q∈Q

#δ(q, a) ­ 1

Automat skończony A jest deterministyczny:

(i) ∀

q∈Q

#δ(q, ε) = 0

(ii) ∀

a∈Σ

∀

q∈Q

#δ(q, a) ¬ 1

Automat skończony A jest deterministyczny i zupełny:

(i) ∀

q∈Q

#δ(q, ε) = 0

(ii) ∀

a∈Σ

∀

q∈Q

#δ(q, a) = 1

Automat skończony zupełny nazywamy automatem Rabina-Scotta. Natomiast automat skończony, determi-

nistyczny oraz zupełny nazywa się deterministycznym automatem Rabina-Scotta.

2.1

Równoważność skończonych automatów deterministycznych oraz niedetermi-
nistycznych

Niech A = {Q, Σ, δ, q

0

, F } będzie deterministycznym automatem skończonym. Język automatu A to słowa

należące do L(A):

L(A) = {w | ˆ

δ(q

0

, w) ∈ F }.

Język automatu A to zbiór łańcuchów w przeprowadzających stan początkowy q

0

w jeden ze stanów akceptują-

cych. Jeśli L = L(A) dla pewnego automatu A, to o języku L możemy powiedzieć, że jest językiem regularnym.

Język dla niedeterministycznego automatu skończonego, również można określić w podobny sposób. Fakt iż

automat ten znajduje się w wielu stanach naraz nie przeszkadza, gdy na pracę automatu spojrzy się całościowo.

9

Zawsze istnieje możliwość, że automat przejdzie do stanu akceptującego. Toteż, jeśli A = {Q, Σ, δ, q

0

, F } jest

automatem niedeterministycznym, to:

L(A) = {w | ˆ

δ(q

0

, w) ∈ F 6= ∅}.

Dodać należy jeszcze, że L(A) jest zbiorem słów w ∈ Σ

∗

takich, że ˆ

δ(q

0

, w) zawiera co najmniej jeden stan

akceptujący.

Dowód iż automaty deterministyczny może realizować dowolny automat niedeterministyczny obejmuje tzw.

konstrukcję podzbiorów. Konstrukcja podzbiorów rozpoczyna od definicja automaty niedeterministycznego
N = {Q

N

, Σ, δ

N

, q

0

, F

N

}. Głównym celem jest znalezienie takiej definicji automaty deterministycznego D =

{Q

D

, Σ, δ

D

, {q

0

}, F

D

} takiego, że L(D) = L(N ). Alfabety wejściowe obydwu automatów są takie same, a stan

początkowy D to zbiór zawierający jeden stan początkowy automatu N . Pozostałe elementy automatu D kon-
struuje się według następujących reguł:

• Q

D

jest zbiorem wszystkich podzbiorów Q

N

(zbiorem potęgowym Q

N

), ogólnie Q

D

może posiadać 2

n

stanów ale stany nieosiągalne można pominąć,

• F

D

jest zbiorem podzbiorów S zbioru Q

N

takich, że S ∩ F

N

6= ∅, co oznacza, że F

D

to zbioru stanów N

zawierających co najmniej jeden stan akceptujący automatu N ,

• dla każdego zbioru S ⊆ Q

N

oraz dla każdego symbolu wejściowego a ∈ Σ

δ

D

(S, a) =

[

p∈S

δ

N

(p, a).

Powyższa równość sugeruje iż aby obliczyć wartość δ

D

(S, a), należy przyjrzeć się wszystkim stanom p ∈ S,

dla których automat N ze stanu p przechodzi do stanu a oraz bierzemy sumę teoriomnogościową tych
stanów.

Technika zamieniania niedeterministycznego automat na automat deterministyczne za pomocą podzbiór jest

dość prosta. Automatu z rysunku

4

posiada zbiór złożony z trzech stanów {q

0

, q

1

, q

2

} to oznacza iż automat

deterministyczny będzie zawierał co najwyżej 2

3

= 8 stanów. Należy wypisać wszystkie stany oraz poprzez ana-

lizę automatu niedeterministycznego wyznaczyć przejścia do wszystkich pozostałych stanów. Poniższy rysunek
prezentuje taką tabelę:

0

1

∅

∅

∅

→ {q

0

}

{q

0

, q

1

}

{q

0

}

{q

1

}

∅

{q

2

}

?{q

2

}

∅

∅

{q

0

, q

1

}

{q

0

, q

1

}

{q

0

, q

2

}

?{q

0

, q

2

}

{q

0

, q

1

}

{q

0

}

?{q

0

, q

2

}

∅

{q

2

}

?{q

0

, q

1

, q

2

}

{q

0

, q

1

}

{q

0

, q

2

}

Choć tabela opisuje stany automatu niedeterministycznego, to fakt iż zgromadzone zostały wszystkie możliwe

stany, powoduje że w istocie mamy już do czynienia z automatem deterministycznym. Wygodnie będzie zamienić
poszczególne zbiory na etykiety, np.: ∅ oznaczymy literą A a zbiór {q

0

, q

1

} literą D. Nowa wersja tabeli funkcji

przejścia po podmianie oznaczeń prezentuje się następująco:

0

1

A

A

A

→ B

E

B

C

A

D

? D

A

A

E

E

F

? F

E

B

? G

A

D

? H

E

F

10

Jeśli prześledzi się dokładnie pracę automatu począwszy od stanu B, okaże się iż i ośmiu wszystkich możli-

wych stanów, osiągalne są tylko trzy B, E oraz F . Pozostałe pięć stanów są nieosiągalne i mogą zostać pominięte.
Ta technika budowy stanu deterministycznego, wymaga jednak wykładniczej ilości kroków w budowie pierwszej
wersji tabeli funkcji przejścia.

Można spróbować wyeliminować taki sposób budowy, poprzez „leniwe” obliczanie za pomocą funkcji przejścia

oraz wykorzystać indukcję. Niech N będzie automatem niedeterministycznym przedstawionym na rysunku

4

.

Podstawa: Jednoelementowy zbiór złożony tylko ze stanu początkowego automatu N jest osiągalny.
Krok Indukcyjny: Zakładając że zbiór S stanów jest osiągalny, należy obliczyć dla każdego symbolu a zbiór
stanów za pomocą funkcji przejścia δ

D

(S, a). Naturalnie otrzymane stany także będą osiągalne.

Ponieważ {q

0

} jest już stanem automatu deterministycznego D (krok podstawowy), to obliczając wartość

funkcji przejścia odpowiednio otrzymamy, δ

D

({q

0

}, 0) = {q

0

, q

1

} oraz δ

D

({q

0

}, 1) = {q

0

}. Wartości te znajdują

także w tabeli funkcji przejścia przedstawionej wcześniej, ale można, a nawet należy, je odczytać z diagramu
automatu N – rysunek

4

.

Stan {q

0

} to już analizowany przez nas, nowym stanem jaki otrzymaliśmy jest {q

0

, q

1

}. Obliczając jego

przejścia odpowiednio otrzymamy: δ

D

({q

0

, q

1

}, 0) = {q

0

, q

1

} oraz δ

D

({q

0

, q

1

}, 1) = {q

0

, q

2

} dokładniej obliczenia

przyjmują następującą postać:

δ

D

({q

0

, q

1

}, 0) = δ

N

(q

0

, 0) ∪ δ

N

(q

1

, 0) = {q

0

, q

1

} ∪ ∅ = {q

0

, q

1

},

δ

D

({q

0

, q

1

}, 1) = δ

N

(q

0

, 1) ∪ δ

N

(q

1

, 1) = {q

0

} ∪ {q

2

} = {q

0

, q

2

}.

Nowym stanem jest {q

0

, q

2

}, z obliczeń wartości funkcji przejścia otrzymamy:

δ

D

({q

0

, q

2

}, 0) = δ

N

(q

0

, 0) ∪ δ

N

(q

2

, 0) = {q

0

, q

1

} ∪ ∅ = {q

0

, q

1

},

δ

D

({q

0

, q

2

}, 1) = δ

N

(q

0

, 1) ∪ δ

N

(q

2

, 1) = {q

0

} ∪ ∅ = {q

0

}.

Ponieważ nie otrzymaliśmy nowych stanów, to procedura się kończy i otrzymaliśmy deterministyczny opis

automatu N. Rysunek

8

przedstawia diagram tego nowego automatu.



{ q 0 }

{ q 0 , q 1 }

s t a r t

0

1

{ q 1 , q 2 }

1

0

0

1

Rysunek 8: Deterministyczny automat skończony akceptujący wyrazy kończące się wyrażeniem 01 zbudowany
z automatu niedeterministycznego z Rysunku

4

Przykład z konwersją automatu niedeterministycznego za pomocą techniki podzbiorów pokazuje iż każdy

automat niedeterministyczny ma odpowiedni automat deterministyczny choć liczba stanów może ulec zmianie
jednak nie będzie większa niż 2

n

(n – liczba stanów automatu niedeterministycznego). Oznacza to iż języki

akceptowany przez obudwa automaty są takie same. Mówi o tym także następujące twierdzenie.

Twierdzenie 1 Jeśli D = {Q

D

, Σ, δ

D

, {q

0

}, F

D

} jest deterministycznym automatem zbudowanym z niedeter-

ministycznego automatu N = {Q

N

, Σ, δ

N

, q

0

, F

N

} za pomocą konstrukcji podzbiorów, to L(D) = L(N ).

Dowód:
Należy dzięki indukcji pokazać, że słowo w:

ˆ

δ

D

({q

0

, w}) = ˆ

δ

N

({q

0

, w})

Należy zwrócić uwagę na to iż co prawda obydwie funkcje ˆ

δ zwracają zbiór stanów z Q

N

, przy czym ˆ

δ

D

interpretuje ten zbiór jako jeden ze stanów Q

D

(będącego zbiorem potęgowym Q

N

), natomiast ˆ

δ

N

interpretuje

ten sam zbiór jako podzbiór Q

N

.

11

Podstawa: Niech |w| = 0, tzn. w = ε. Na podstawie definicji ˆ

δ dla determistycznych i niedeterministycznych

automatów wiemy iż ˆ

δ

D

({q

0

}, ε) = ˆ

δ

N

({q

0

}, ε) = {q

0

}.

Krok indukcyjny: Niech |w| = n + 1 oraz niech stwierdzenie będzie prawdziwe dla wejść o długości n. Jeśli
w = xa, gdzie a jest ostatnim symbolem w, to na mocy założenia indukcyjnego ˆ

δ

D

({q

0

}, x) = ˆ

δ

N

({q

0

}, x). Niech

oba te zbiory stanów N mają postać {p

1

, p

2

, . . . , p

k

}.

Definicja ˆ

δ dla automatu niedeterministycznego pokazuje iż

ˆ

δ

N

(q

0

, w) =

k

[

i=1

ˆ

δ

N

(p

i

, a).

Natomiast konstrukcja podzbiorów pokazuje

δ

D

({p

1

, p

2

, . . . , p

k

}, a) =

k

[

i=1

ˆ

δ

N

(p

i

, a).

Korzystajac z konstrukcji podzbiorów oraz z faktu, że ˆ

δ

D

({q

0

}, x) = {p

1

, p

2

, . . . , p

k

} w części indukcyjnej definicji

ˆ

δ dla automatów deterministycznych:

ˆ

δ

D

({q

0

}, x) = δ

D

(ˆ

δ

D

({q

0

}, x), a) = δ

D

({p

1

, p

2

, . . . , p

k

}, a) =

k

[

i=1

ˆ

δ

N

(p

i

, a).

W ten sposób dowiedliśmy, że ˆ

δ

D

({q

0

, w}) = ˆ

δ

N

({q

0

, w}). Automaty D oraz N akceptują słowo w wtedy i tylko

wtedy, gdy odpowiednio ˆ

δ

D

({q

0

}, w) i ˆ

δ

N

({q

0

}, w) zawierają stan z F

N

.



Następne twierdzenie uogólnia przedstawione powyżej twierdzenie:

Twierdzenie 2 Niech L będzie zbiorem akceptowanym przez niedeterministyczny automat skończony. Wtedy
istnieje deterministyczny automat skończony akceptujący L.

Szkic dowodu:
Ponieważ w twierdzeniu zostało użyte wyrażenie „wtedy i tylko wtedy”, oznacza to iż należy dowód podzielić
na dwie implikacje. Pierwsza implikacja ⇐ oznacza iż automat niedeterministyczny jest zamieniany na automat
deterministyczny. A jest to nic innego, jak konstrukcja podzbiorów i twierdzenie które zostało omówione powyżej.

Można wobec tego przejść do drugiej części dowodu, implikacji ⇒. Należy zamienić automat deterministycz-

ny na identyczny automat niedeterministyczny. Co sprowadza się do intuicyjnego interpretowania diagramu
przejść automatu deterministycznego jako automatu niedeterministycznego. Automat niedeterministyczny bę-
dzie posiadał tylko i wyłącznie jedno przejście. Formalnie, należy pokazać na poziomie funkcji przejścia, że dla
deterministycznego automatu D = {Q

D

, Σ, δ

D

, q

0

, F

D

} określamy równoważny automat niedeterministyczny

N = {Q

N

, Σ, δ

N

, q

0

, F

N

}, w którym funkcja przejścia δ

N

jest określona przez regułę:

δ

D

(q, a) = p ⇒ δ

N

(q, a) = {p}

Względnie łatwo pokazać dzięki indukcji, długości słowa w, iż jeśli ˆ

δ

D

(q

0

, a) = p, to

ˆ

δ

N

(q

0

, a) = {p}.

Takie podejście oznacza iż w jest akceptowane przez D wtedy i tylko wtedy, gdy jest ono akceptowany przez
automat N , co oznacza L(D) = L(N ).



2.2

Konwersja automatu z przejściami ε na automat deterministyczny

Sposób eliminacji przejść ε oraz konwersja automaty niedeterministycznego na deterministyczny jest podobny
do konstrukcji podzbiorów ale wykorzystywane jest także ε-domknięcie. Równoważny automat deterministyczny
D = {Q

D

, Σ, δ

D

, q

0

, F

D

} jest budowany w oparciu o automat E = {Q

E

, Σ, δ

E

, q

0

, F

E

} w następujący sposób:

1. Q

D

jest zbiorem podzbiorów Q

E

. Wszystkie osiągalne stany D są ε-domkniętymi podzbiorami Q

E

, tj.

zbiorami S ⊆ Q

E

takimi, że S = ED(S).

2. q

D

= ED(q

0

), stan początkowy D otrzymujemy, poprzez domknięcie zbioru złożonego jedynie ze stanu

początkowego E.

12

3. F

D

składa się ze zbiorów stanów, które zawierają co najmniej jeden stan akceptujący E, F

D

= {S | S ∈

Q

D

oraz S ∩ F

E

6= ∅}.

4. Dla wszystkich a ∈ Σ oraz S ⊆ Q

D

wartość funkcji przejścia δ(S, a) jest obliczana w następujący sposób:

(a) S = {p

1

, p

2

, p

3

, . . . , p

k

},

(b) następnie należy wyznaczyć

S

k
i=1

δ

E

(p

i

, a), wynikiem niech będzie zbiór {r

1

, r

2

, r

3

, . . . , r

m

},

(c) wtedy, wartość nowej funkcji przejścia jest określona jako δ

D

(S, a) =

S

m
j=1

ED(r

j

).

Automat z rysunku

6

po konwersji może przyjąć postać podobną do diagramu ukazanego na rysunku

9

.

Na tym diagramie został pominięty martwy stan ∅ i wszystkie przejścia do tego stanu. Zastosowanie reguł
wymienionych powyżej rozpoczynamy od stanu początkowego q

0

. Po konwersji stanem początkowym nowego

automatu deterministycznego jest ED(q

0

) = {q

0

, q

1

}. Następnie należy wyznaczyć na które stany przechodzą

stany q

0

i q

1

. Rysunek

6

pokazuje iż stan q

1

nie przechodzi na żaden inny stan przy znakach plus i minus.

Jednak q

0

przechodzi na stan q

1

. Z tego powodu aby obliczyć δ

D

({q

0

, q

1

}, +), zaczynamy od {q

1

} i obliczamy

ε-domknięcie. Ponieważ nie ma ε przejść z q

1

, to wartość funkcji przejścia δ

D

({q

0

, q

1

}, +) = {q

1

}. Podobna

sytuacja następuje w przypadku drugiego symbolu δ

D

({q

0

, q

1

}, −) = {q

1

}.

Kolejny etap to obliczenie wartości δ

D

({q

0

, q

1

}, .). Diagram pokazuje że stan q

0

nie przechodzi na nic innego

przy kropce, ale q

1

przechodzi na stan q

2

. Oznacza to konieczność obliczenia ε-domknięcia q

2

. Nie ma ε-przejść

z q

2

, więc ten stan jest swym własnym domknięciem, ostatecznie w tym przypadku δ

D

({q

0

, q

1

}, .) = {q

2

}.

Zakończenie analizy stanu początkowego wymaga obliczenie wartości funkcji przejścia dla cyfr, dobrym

przykładem będzie cyfra zero: δ

D

({q

0

, q

1

}, 0). Ze stanu q

0

przy pomocy cyfry nie przejdziemy do żadnego innego

stanu. Jednakże przejście następuje przy stanie q

1

, ponownie do stanu q

1

oraz q

4

. Obliczenie wartości funkcji

przejścia jest dość łatwe, ponieważ nie ma przejść ε: δ

D

({q

0

, q

1

}, 0) = {q

1

, q

4

}. Wartość dla pozostałych cyfr jest

identyczna.

Dla pozostałych stanów sposób wyznaczania przejść jest podobny. Warto zwrócić uwagę iż w oryginalnym

automacie mamy stan akceptujący q

5

. Jednak w wyniku konwersji otrzymamy dwa stany akceptujące {q

3

, q

5

}

oraz {q

2

, q

3

, q

5

}.

{ q 0 , q 1 }

s t a r t

{ q 1 }

{ q 1 , q 4 }

{ q 2 }

{ q 3 , q 5 }

{ q 2 , q 3 , q 5 }

c y f r a

.

+ , -

c y f r a

.

.

c y f r a

c y f r a

c y f r a

c y f r a

Rysunek 9: Deterministyczny automat pozbawiony przejść ε zbudowany na podstawie

6

2.3

Równoważność skończonych automatów deterministycznych oraz automatów
przejściami ε

Wprowadzenie pustego przejścia ε nie powoduje iż automaty z takimi przejściami mogą rozpoznawać inne języki.
Każdy tego typu automat można zamienić na odpowiedni deterministyczny automat. Dalszy wniosek zapisany
w postaci twierdzenia, dotyczy rozpoznawania języków:

Twierdzenie 3 Język L jest akceptowany przez pewien niedeterministyczny automat z przejściami ε wtedy i
tylko wtedy, gdy L jest akceptowany przez pewien deterministyczny automat.

Dowód: Należy sprawdzić dwie implikacje. W pierwszej kolejności zostanie przeanalizowana implikacja ⇐.
Zakładamy, że L = L(D) dla pewnego automatu deterministycznego D. Automat deterministyczny dość łatwo
zamienić na odpowiedni automat niedeterministyczny z przejściami ε. Dodajemy dodatkowe przejścia δ(q, ε) =
∅ do wszystkich stanów q automatu deterministycznego. Należy także przekształcić przejścia na symbolach

13

automatu D w taki sposób aby dla δ

D

(q, a) = p, funkcja przejścia automatu niedeterministycznego E miała

postać δ

E

(q, a) = {p}. Po tej zamianie przejścia są takie same ale brakuje jawnych ε-przejść. Nie stanowi to

jednak o żadnym błędzie, czy niedopatrzeniu.

Druga implikacja ⇒ dla automatu niedeterministycznego E = {Q

E

, Σ, δ

E

, q

0

, F

E

} z ε-przejściami wymaga

zastosowania zmodyfikowanej konstrukcji podzbiorów aby otrzymać D = {Q

D

, Σ, δ

D

, q

D

, F

D

}. W ten sposób

chcemy wykazać iż L(D) = L(E). W tym celu należy wykazać równoważność rozszerzonych funkcji przejścia

ˆ

δ

E

(q

0

, w) = ˆ

δ

D

(q

D

, w), za pomocą indukcji po długości słowa w.

Podstawa: Jeśli |w| = 0, to naturalnie w = ε. Wiemy, że ˆ

δ

E

(q

0

, ε) = ED(q

0

). Natomiast stan początkowy

został zdefiniowany jako q

D

= ED(q

0

) . Ostatecznie wiadomo, że dla dowolnego deterministycznego automatu

ˆ

δ

D

(p, ε) = p dla dowolnego stanu p, a więc w szczególności ˆ

δ

D

(q

0

, ε) = ED(q

0

). Co kończy pierwszą część dowodu

iż ˆ

δ

E

(q

0

, ε) = ˆ

δ

D

(q

D

, ε).

Krok indukcyjny: Niech słowo w = xa, gdzie a jest ostatnim symbolem. Zakładamy, że rozważane twierdzenie
jest prawdziwe dla x. Oznacza to, że ˆ

δ

E

(q

0

, x) = ˆ

δ

D

(q

D

, x) a wartością obydwu funkcji niech będzie zbiór

{p

1

, p

2

, . . . , p

k

}. Korzystając z definicji ˆ

δ dla automatu niedeterministycznego z przejściami ε będziemy obliczać

wartość funkcji ˆ

δ

E

(q

0

, w) w następujący sposób:

1.

S

k
i=1

δ

E

(p

i

, a) = {r

1

, r

2

, . . . , r

m

},

2. ˆ

δ

E

(q

0

, w) =

S

m
j=1

ED(r

j

).

Odwołując się w tym miejscu do konwersji automatu niedeterministycznego na deterministyczny bez ε-przejść,
zobaczymy że δ

D

({p

1

, p

2

, . . . , p

k

}, a) konstruuje się za pomocą dwóch kroków wymienionych powyżej. Co pozwala

stwierdzić, że ˆ

δ

D

(q

D

, w), jest tożsama z δ

D

({p

1

, p

2

, . . . , p

k

}, a) oraz ze zbiorem generowanym przez ˆ

δ

E

(q

0

, w).

W ten sposób dowiedziono, że ˆ

δ

E

(q

0

, w) = ˆ

δ

D

(q

D

, w). 

3

Wyrażenia regularne

Niech Σ będzie skończonym zbiorem symboli i niech L, L

1

, L

2

, będą zbiorami łańcuchów z Σ

∗

. Złożeniem L

1

,

L

2

, oznaczanym L

1

L

2

, nazywamy {xy | x ∈ L

1

, y ∈ L

2

}. Innymi słowy, łańcuchy należące do L

1

L

2

są tworzone

poprzez wszystkie kombinacje elementów z łańcucha L

1

z elementami łańcucha L

2

. Niech L

0

= {λ} i L

i

= LL

i−1

dla i ­ 1. Domknięciem Kleene’go L oznaczonym przez symbol L

∗

, nazywamy zbiór:

L

∗

=

∞

[

i=0

L

i

Natomiast domknięciem dodatnim L, oznaczonym symbolem L

+

, jest zbiór:

L

+

=

∞

[

i=1

L

i

Inaczej mówiąc zbiór L

∗

to wszystkie słowa po złożeniu dowolnej liczby słów z L. Podobnie zbiór L

+

jednak

nie zalicza się tu słów pustych z elementem λ.

Przykład 1 Niech L

1

= {10, 1} oraz L

2

= {011, 11}. Wtedy L

1

L

2

= {10011, 1011, 111}. Ponadto {10, 11}

∗

=

{λ, 10, 11, 1010, 1011, 1110, 1111, . . .}

Niech Σ będzie alfabetem. Wyrażenia regularne nad zbiorem Σ są zdefiniowane w następujący sposób:

1. ∅ jest wyrażeniem regularnym reprezentującym zbiór pusty

2. λ wyrażeniem regularnym reprezentującym zbiór {λ}

3. Dla każdego a ∈ Σ, a jest wyrażeniem regularnym reprezentującym zbiór {a}

4. Jeżeli r i s są wyrażeniami regularnymi reprezentującymi języki R i S to (r + s) (alternatywny zapis (r|s)),

(rs), (r

∗

) są wyrażeniami regularnymi reprezentującymi odpowiednio zbiory R ∪ S, RS i R

∗

.

14

Zapis wyrażeń regularnych warto uprościć poprzez wprowadzenie kilku założeń. Jeśli, operator ∗ ma wyższy
priorytet niż złożenie lub +, oraz jeśli złożenie ma wyższy priorytet niż + to wyrażenie ((0(1

∗

)) + 0) można

zapisać jako 01

∗

+ 0. Efektem przyjęcia priorytetów jest możliwość opuszczenia zbędnych nawiasów. Wyrażenia

typu rr

∗

można skracać do r

+

. Zakładamy także, że r

i

= rrrrr . . . rrr

|

{z

}

i razy

.

Podsumowując w wyrażeniach regularnych stosujemy następujące priorytety operatorów:

1. ( ) - najwyższy priorytet,

2. ∗

3. · - (złożenie)

4. + - najniższy priorytet.

Przykład 2 Wyrażenie 00 jest wyrażeniem regularnym reprezentującym {00}. Wyrażenie (0 + 1)

∗

reprezentuje

wszystkie słowa złożone z zer oraz jedynek. Inne wyrażenie (0 + 1)

∗

00(0 + 1)

∗

opisuje zbiór wszystkich łańcuchów

zer oraz jedynek, zawierających przynajmniej dwa kolejne zera. Wyrażenie (1+10)

∗

to zbiór wszystkich łańcuchów

zer oraz jedynek które rozpoczynają się od jedynki ale nie zawierają dwóch kolejnych zer. Przykładem jest słowo
1101011 które, jeśli podzielimy na 1 − 10 − 10 − 1 − 1 jasno wskazuje iż jest słowem generowanym przez (1 + 10)

∗

.

Wyrażenie (0 + 1)

∗

011 opisuje wszystkie łańcuchy zer i jedynek kończące się 011. Słowa generowane przez

wyrażenie 0

∗

1

∗

2

∗

to dowolnej długości ciągi zer. a następnie jedynek i na końcu dwójek. Podobnym wyrażenie

00

∗

11

∗

22

∗

które jest podobne jak poprzednie ale gwarantuje, że zawsze będzie przynajmniej jedno zero, jedna

jedynka bądź dwójka. Nieco bardziej skrótowo można to zapisać jako 0

+

1

+

2

+

.

3.1

Prawa algebry zbiorów/języków regularnych

Niech p, q i r będą dowolnymi wyrażeniami regularnymi. Prawdziwe są następujące zależności i tożsamości:

p|q = q|p

p|(q|r) = (p|q)|r

p(qr) = (pq)r

pq|pr = p(q|r)

pq|rq = (p|r)q

λp = pλ = p

∅p = p∅ = ∅

λ

∗

= λ

∅

∗

= λ

p

∗

= p|p

∗

= (p|λ)

∗

(p

∗

)

∗

= p

∗

p|p = p

p|∅ = p

λ|p

∗

= p

∗

λ|pp

∗

= p

∗

λ|p

∗

p = p

∗

pqq

∗

|pq

∗

= pq

∗

(p|q)

∗

= (p

∗

|q

∗

)

∗

= (p

∗

q

∗

)

∗

Przykład 3 Dla przykładu zostanie udowodnione przedostatnie prawo z przedstawionej listy:

abb

∗

|ab

∗

= ab

∗

ponieważ:

abb

∗

|ab

∗

= (ab)(b)

∗

∪ (a)(b)

∗

= (ab, abb, abbb, ...) ∪ (a, ab, abb, ...) = (a, ab, abb, ...) = (a)(b)

∗

4

Zadania

1. Udowodnić twierdzenie

1

.

2. Udowodnić twierdzenie

2

.

3. Udowodnić twierdzenie

3

.

4. Podać formalny opis oraz tabelę przejścia dla funkcji δ dla dwóch następujących automatów:

• deterministyczny automat akceptujący liczby rzeczywiste zapisane w notacji o następującym przy-

kładzie 10.23E − 14:

15

3

s t a r t

1

4

2

7

8

5

9

c y f r a

c y f r a

c y f r a

c y f r a

k r o p k a

c y f r a

E

c y f r a

c y f r a

c y f r a

p l u s a l b o

m i n u s

p l u s a l b o

m i n u s

• deterministyczny automat rozpoznawający następujące wyrażenie regularne (a|b)

∗

bb:

3

2

1

0

s t a r t

b

a

a

a

a

b

b

b

5. Automat niedeterministyczny o następującej tabeli przejścia:

0

1

→ p

{p, q}

{p}

q

{r}

{r}

r

{s}

∅

? s

{s}

{s}

zamienić na automat deterministyczny.

6. Automat niedeterministyczny o następującej tabeli przejścia:

0

1

→ p

{q, s}

{q}

? q

{r}

{q, r}

r

{s}

{p}

? s

∅

{p}

zamienić na automat deterministyczny.

7. Dla automatu niedeterministycznego z przejściami ε o następującej tabeli przejścia:

ε

a

b

c

→ p

∅

{p}

{q}

{r}

q

{p}

{q}

{r}

∅

? r

{q}

{r}

∅

{p}

(a) Obliczyć ε-domknięcie dla każdego stanu.

(b) Podać wszystkie łańcuchy o długości co najwyżej trzy akceptowane przez ten automat.

(c) Przekształcić automat na automat deterministyczny.

8. Dla automatu niedeterministycznego z przejściami ε o następującej tabeli przejścia:

ε

a

b

c

→ p

{q, r}

∅

{q}

{r}

q

∅

{p}

{r}

{p, q}

? r

∅

∅

∅

∅

(a) Obliczyć ε-domknięcie dla każdego stanu.

(b) Podać wszystkie łańcuchy o długości co najwyżej trzy akceptowane przez ten automat.

(c) Przekształcić automat na automat deterministyczny.

16

9. Zaprojektować deterministyczne automaty rozpoznające słowa kluczowe:

(a) while,

(b) for,

(c) begin,

(d) program.

10. Zaprojektować niedeterministyczne automaty rozpoznające słowa kluczowe:

(a) while,

(b) for,

(c) begin,

(d) program.

11. Zaprojektować jeden deterministyczny automat rozpoznający słowa kluczowe:

(a) while,

(b) for,

(c) begin,

(d) program.

12. Zaprojektować jeden niedeterministyczny automat rozpoznający słowa kluczowe:

(a) while,

(b) for,

(c) begin,

(d) program.

13. Pokazać, dlaczego automat o następującym diagramie

q 0

q 1

q 2

...

1

0 , 1

....

q n

0 , 1

s t a r t

0 , 1

0 , 1

0 , 1

który rozpoznaje słowa którego N-tym symbolem od końca jest jedynka, nie ma równoważnego determi-
nistycznego automatu o liczbie stanów znacznie mniejszej niż 2

n

.

14. Zdefiniować automaty skończone i deterministyczne które będą akceptować (rozpoznawać) języki opisy-

wane przez poniższe wyrażenia regularne

(a) (aa|bb)

∗

(ab|ba)

∗

(aa|bb)

∗

(b) b(ab|ba)

∗

(aa|bb)

∗

a

(c) (ab|ba)

∗

(bb|aa)

∗

(ab|ba)

∗

(d) a(aa|bb)

∗

(ab|ba)

∗

b

15. Zbudować deterministyczny automat skończony akceptujący język nad alfabetem T = 0, 1

(a) będący zbiorem wszystkich łańcuchów zerojedynkowych z wyjątkiem łańcucha 0110,

(b) będący zbiorem wszystkich łańcuchów zerojedynkowych nie zawierających łańcucha 1010,

(c) będący zbiorem wszystkich łańcuchów zerojedynkowych zawierających co najwyżej jeden raz łańcuch

101.

17

16. Podać jakie wyrażenia regularne są akceptowane przez poniższe deterministyczne automaty:

(a)

4

2

1

3

s t a r t

c

a

b

c

c

b

b

a

b

c

a

a

(b)

3

2

1

5

s t a r t

c

c

b

a

b

a

a

4

b

c

c

b

b

a

a

c

(c)

B

D

A

s t a r t

0

0

1

0

C

1

0

1

1

(d)

C

D

s t a r t

0

A

1

B

1

0

0

1

1

0

5

Dalsze informacje

Poniższe pozycje odnoszą się do wszystkich list z ćwiczeniami z przedmiotu teoretyczne podstawy informatyki.

Literatura

[1]

David Harel: Rzecz o istocie informatyki Algorytmika, Edycja polska Wydanie drugie, Wydawnictwa
Naukowo-Techniczne 2000.

[2]

Tomasz Bilski, Krzysztof Chmiel, Janusz Stokłosa: Zbiór zadań ze złożoności obliczeniowej algorytmów,
Politechnika Poznańska 1992.

[3]

Janusz Stokłosa: Zadania ze złożoności obliczeniowej algorytmów, Politechnika Poznańska 1989.

[4]

L. Banachowski, Antoni Kreczmar: Elementy analizy algorytmów, Wydawnictwa Naukowo-Techniczne
1982.

[5]

John E.Hopcroft, Jeffrey D.Ullman: Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnic-
two Naukowe PWN 2003 Wydanie 1 oraz Wydanie 2 z roku 2006.

[6]

Mordechai Ben-Ari: Logika matematyczna w informatyce, Wydawnictwa Naukowo-Techniczne 2005.

[7]

Christos H.Papadimitriou: Złożoność obliczeniowa, Wydawnictwa Naukowo-Techniczne 2002.

[8]

R.L. Graham, D.E. Knuth, O.Patashnik: Matematyka konkretna,Wydawnictwo Naukowe PWN 2002.

[9]

Kenneth A.Ross, Charles R.B.Wright: Matematyka dyskretna, Wydawnictwo Naukowe PWN 2000.

[10]

Piotr Wróblewski,: Algorytmy struktury danych i techniki programowania, Helion 1997.

[11]

Materiały ze strony dr inż. Janusza Majewskiego dotyczące przedmiotu „Automaty i języki formalne”.

18