Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Literatura
Polskie wydanie:
Automaty skończone: DAS i NAS
J.E. Hopcroft, R. Motwani, J.D. Ullman Wprowadzenie do
teorii automatów, języków i obliczeń, PWN, Warszawa
2005
Dane oryginału:
J.E. Hopcroft, R. Motwani, J.D. Ullman Introduction to
15 listopada 2008 / Wykład
Automata Theory, Languages and Compuations, Pearson
Education, publishing as Addison-Wesley Higher
Education 2001
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Ogólnie o automatach
Outline Zastosowanie
1
Wprowadzenie
Ogólnie o automatach
Pojęcia podstawowe
Automaty skończone są formalnym modelem matematycznym
Automat skończony  przedstawienie nieformalnie
dla następujących zastosowań
2
DAS
Definicja i przykłady
Projektowanie układów cyfrowych (sterowniki)
Automat Skończony (AS) a napisy
Analizator leksykalny w kompilatorze
Ć
Rozszerzona funkcja przejścia �
Wyszukiwanie słów w pliku (lub internecie)
3
NAS
Zaawansowane oprogramowanie do weryfikacji systemów
Spojrzenie nieformalne, definicja, przykład
o skończonej liczbie stanów
Ć
Rozszerzona funkcja przejścia �
4
Równoważność DAS i NAS Teoria języków i obliczeń
Wstęp
Konstrukcja równoważnego DAS
Twierdzenia i dowody
Zły przypadek konstrukcji podzbiorów
5
Zastosowanie
Przeszukiwanie tekstu
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Ogólnie o automatach Ogólnie o automatach
Przykłady Reprezentacje strukturalne
Istnieją dwie ważne notacje, które odgrywają ważną rolę w
badaniu automatów i ich zastosowań
Automat skończony modelujący przełącznikon/off
Naciśnij
Gramatyki to modele pożyteczne przy projektowaniu
oprogramowania przetwarzającego dane o strukturze
Start
rekurencyjnej (np. program "parser") np. E => E + E
on off
Wyrażenia regularne reprezentują strukturę danych,
szczególnie łańcuchy tekstu, np. wzorzec
Naciśnij
 [A-Z][a-z]*[ ][A-Z][A-Z]
Automat skończony rozpoznający ciąg znakówthen
pasuje do
Start t h e n
t th the then Ithaca NY
Pytanie: jaki wzorzec byśmy utworzyli dla napisuPalo
Alto CA?
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Pojęcia podstawowe Pojęcia podstawowe
Alfabety, napisy, napis pusty Długość napisu, potęgi alfabetu
Długość napisu to ilość wystąpień symboli alfabetu w
Alfabet jest to skończony niepusty zbiór symboli
ciągu znaków
Przykład 1: = {0, 1} alfabet binarny (zerojedynkowy)
|w| oznacza długość napisu w
Przykład 2: = {a, b, c, . . . , z} alfabet składający się z
|0110| = 4, | | = 0
małych liter
Potęga alfabetu to zbiór napisów od długości k nad
Przykład 3: zbiór znaków kodu ASCII
k
symbolami alfabetu . Oznaczany jest przez
Ciąg znaków (napis) to skończona sekwencja symboli
Przykład: = {0, 1}
alfabetu , np.: 0011001
1
= {0, 1}
Napis pusty to ciąg znaków z zerowym wystąpieniem 2
= {00, 01, 11, 10}
symboli alfabetu 0
=
Napis pusty oznaczany jest przez
3
Pytanie: ile napisów jest w zbiorze potęgowym
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Pojęcia podstawowe Pojęcia podstawowe
Domknięcie Kleene go, konkatenacja Języki
"
Język Jeżeli jest alfabetem oraz L ą" to L jest
Zbiór wszystkich napisów nad alfabetem jest oznaczany
"
językiem. Czyli język to zbiór napisów
jako i jest nazywany domknięciem Kleene go, czyli:
" 0 1 2 Przykłady języków:
= *" *" � � �
Zbiór słów języka polskiego
oraz
Zbiór poprawnych programów w języku C
+ 1 2
= *" � � �
Zbiór napisów składających się z n zer po których
" +
= *"{ }
występują n jedynek: { , 01, 0011, 000111, . . .}
Zbiór napisó o równej ilości zer i jedynek:
Konkatenacja (łączenie) Jeżeli x i y są napisami,
{ , 01, 10, 0011, 0101, 1010 . . .}
wówczas xy jest napisem otrzymanym poprzez
LP = zbiór liczb binarnych, których wartość jest liczbą
umieszczenie kopii napisu y bezpośrednio za kopią napisu
pierwszą {10, 11, 101, 111, 1011, . . .}
x. Formalnie:
Język pusty "
x = a1a2 . . . ai, y = b1b2 . . . bj
Język { } składający się z napisu pustego
xy == a1a2 . . . aib1b2 . . . bj
Uwaga: " = { }

Przykład: x = 01101, y = 110, xy = 01101110
Uwaga 2: alfabet nad którym jest określony język, jest
Uwaga: dla każdego napisu x zachodzi x = x = x
zawsze zbiorem skończonym
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Pojęcia podstawowe Pojęcia podstawowe
Problemy (1) Problemy (2)
Nasze obiegowe wyobrażenie o problemach różni się od
traktowania problemów jako problemów decyzyjnych, których
Problem W teorii automatów problem to kwestia "Czy dany
celem jest udzielenie odpowiedzitaklubnie. O problemach
napis w należy do języka L?". Wszystko co potocznie
myślimy raczej jak o transformacji, która przetwarza dane
nazywamy "problemem", daje się wyrazić jako należenie od
wejściowe na dane wyjściowe.
pewnego języka
Przykład: problem "skompiluj program w języku C" jest
Przykład: pytanie problemowe "Czy dana liczba binarna jest
równoważne problemowi "sprawdz
czy program jest poprawny i
liczbą pierwsza?" jest równoważne problemowi "Czy ta dana
jeżeli tak, to utwórz jego drzewo rozbioru"
liczba jest elementem zbioru LP"
Niech LX będzie zbiorem wszystkich poprawnych programów w
Czy 11101 " LP? Jakie zasoby obliczeniowe (pamięć, ilość
języku programowania X . Jeżeli możemy pokazać, że
działań czyli czas) są potrzebne aby udzielić odpowiedzi na to
przynależność do zbioru LX jest trudne, wówczas parsowanie
pytanie?
programów napisanych w X nie może być łatwiejsze
Pytanie: dlaczego?
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Automat skończony  przedstawienie nieformalnie Automat skończony  przedstawienie nieformalnie
Przykład protokuł e-biznesowego Protokoły uczestników transakcji
zapłata odbiór przelew
Start
a b d f
Zbiór dopuszczalnych zdarzeń
wysyłka wysyłka wysyłka
Klient możezapłacićsklepowi (czyli wysyła e-pieniądz
do sklepu)
c e g
a) Sklep
odbiór przelew
Klient możeanulowaćzapłatę (e-pieniądze zostają
odesłane spowrotem do banku na konto klienta)
2
anulowanie
zapłata
Sklep możewysłaćtowar do klienta
anulowanie
Sklep możeodebraćz banku e-pieniądz klienta
1 3 4
(spieniężyć)
odbiór przelew
Start
Bank może dokonaćprzelewue-pieniądza do sklepu
Start
b) Klient c) Bank
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Automat skończony  przedstawienie nieformalnie Automat skończony  przedstawienie nieformalnie
Pełny zbiór przejść automatów Automat produktowy dla sklepu i banku
zapłata zapłata zapłata
a b c d e f g
anulowanie anulowanie anulowanie anulowanie
Start
Z Z Z Z Z Z
zapłata odbiór przelew
Start
Z W W W
a b d f
1
O O
wysyłka wysyłka wysyłka
A A A A A A A
c e g
a) Sklep
odbiór przelew
Z W W W
2
zapłata zapłata zapłata
anulowanie anulowanie anulowanie
Z Z Z Z Z Z
zapłata, wysyłka
wysyłka
O Z, A Z, A Z, A
odbiór
przelew Z W W W
2
zapłata zapłata
3
zapłata
odbiór odbiór
anulowanie
anulowanie anulowanie
A Z, A Z, A Z, A
wysyłka wysyłka
anulowanie
O O P P
1 3 4
odbiór przelew
Z W W W
Start
4
Start
b) Klient c) Bank A Z, A Z, A Z, A Z, A Z, A Z, A
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Definicja i przykłady Definicja i przykłady
Deterministyczny Automat skończony (DAS)  def. Deterministyczny Automat Skończony  przykład 1
Deterministycznym Automatem Skończonym (DAS) jest
Opis słowny: Automat A, który akceptuje wszystkie ciągi
następująca piątka:
zawierające w sobie 0 po którym występuje 1. Formalnie
ciągi te można określić za pomocą konstruktora zbioru
A = (Q, Ł, �, q0, F )
napisów: L = {x01y : x, y " {0, 1}"}
gdzie:
Definicja formalna: A = ({q0, q1, q2}, {0, 1}, �, q0, {q1})
� 0 1
Q jest skończonym zbiorem stanów
q0 q2 q0
Ł jest skończonym alfabetem (zbiorem symboli
a � zadana jest w postaci tabeli przejść:
q1 q1 q1
wejściowych)
q2 q1 q1
� jest funkcją przejścia odwzorowującą Q � Ł Q
Diagram przejść:
q0 " Q jest stanem początkowym
1 0
F ą" Q jest zbiorem stanów końcowych (akceptujących)
Start
q0 0 q2 1 q1 0,1
Dla zadanego symbolu wejściowego DAS może przejść do co
najwyżej jednego stanu następnego
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Definicja i przykłady Automat Skończony (AS) a napisy
Deterministyczny Automat Skończony  przykład 2 Automat Skończony (AS) a napisy
DAS akceptujący napisy składające się z wyłącznie z parzystej
O AS można powiedzieć, że akceptuje ciąg znaków
liczby 0 i parzystej liczby 1
w = a1a2 . . . an, jeśli w diagramie przejść jest ścieżka, taka że:
1
Start
q0 q1
1
Rozpoczyna się w stanie początkowym
1
0
0
2
Kończy się w stanie akceptującym
3
Składa się z sekwencji etykiet a1a2 . . . an
0
0
Przykład: diagram przejść
q2 1 q3
1
0,1
0 1
Start
q0 0 q1 1 q2
q0 q2 q1
Tablicowa reprezentacja automatu
q1 q3 q0
q2 q0 q3
akceptuje przykładowy napis 101101
q3 q1 q2
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Ć
Rozszerzona funkcja przejścia � Spojrzenie nieformalne, definicja, przykład
Ć
Niedeterministyczny Automat Skończony (NAS)  opis
Rozszerzona funkcja przejścia �
NAS ma możliwość znajdowania się w kilku stanach naraz. W
Pojęcie funkcji przejścia � może być rozszerzone na
pewnym sensie NAS ma zdolność do zgadywania odnośnie
Ć
funkcję �, która, inaczej niż �, nie operuje na stanach i
wejścia, dzięki czemu może wybrać te stany które je akceptują.
symbolach alfabetu, lecz na stanach i ciągach znaków
Przykład: Automat, który akceptuje napisy kończące się na 01
Podstawa:
Ć
�(q, ) = q 0,1
Start
Krok indukcyjny:
q0 0 q1 1 q2
Ć Ć
�(q, xa) = �(�(q, x), a)
A oto co się dzieje, gdy powyższy NAS przetwarza napis 00101
Z powyższego więc wynika, że język akceptowany przez
q0 q0 q0 q0 q0 q0
DAS A można formalnie określić:
q1 q1 q1
brak ruchu
q2 q2
Ć
L(A) = {w : �(q0, w) " F }
brak ruchu
0 0 1 0 1
Języki akceptowane przez automat skończony, nazywane
Dla każdego możliwego stanu następnego tworzy się kopia
sąjęzykami regularnymi
automatu (proliferacja)
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Spojrzenie nieformalne, definicja, przykład Spojrzenie nieformalne, definicja, przykład
Niedeterministyczny Automat Skończony  definicja Niedeterministyczny Automat Skończony  przykład
NAS jest następującą piątka:
Przykład: Automat, który akceptuje napisy kończące się na 01
A = (Q, Ł, �, q0, F )
0,1
gdzie:
Start
q0 0 q1 1 q2
Q jest skończonym zbiorem stanów
Ł jest skończonym alfabetem (zbiorem symboli
Definicja formalna:
wejściowych)
� jest funkcją przejścia odwzorowującą Q � Ł 2Q w
A = ({q0, q1, q2}, {0, 1}, �, q0, {q1})
zbiór potęgowy zbioru stanów, czyli w zbiór wszystkich
możliwych podzbiorów zbioru Q
� 0 1
q0 " Q jest stanem początkowym
q0 {q0, q1} {q0}
a � zadana jest tabelą przejść:
F ą" Q jest zbiorem stanów końcowych (akceptujących)
q1 " {q2}
q2 " "
Dla zadanego symbolu wejściowego NAS może przejść do
zera, jednego lub więcej stanów następnych
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Ć Ć
Rozszerzona funkcja przejścia � Rozszerzona funkcja przejścia �
Ć Ć
Rozszerzona funkcja przejścia �  definicja Rozszerzona funkcja przejścia �  wykorzystanie
Udowodnijmy formalnie, że NAS akceptuje język {x01 : x " Ł"}
Podstawa:
0,1
Ć
�(q, ) = {q}
Start
Krok indukcyjny: q0 0 q1 1 q2
Ć
�(q, xa) = �(p, a)
Można tego dokonać poprzez zastosowanie indukcji wzajemnej
Ć
p"�(q,x)
do trzech poniższych stwierdzeń:
Ć
1
w " Ł" �! q0 " �(q0, w)
Ć
Przykład Policzmy �(q0, 00101) na tablicy
Ć
2
q1 " �(q0, w) �! w = x0
Teraz formalnie możemy określić język akceptowany przez
Ć
NAS jako: 3
q2 " �(q0, w) �! w = x01
Ć
L(A) = {w : �(q0, w) )" F = "}

czyli dowodząc kolejnych stwierdzeń można skorzystać z już
dowiedzionych stwierdzeń poprzednich. Dowiedzenie
stwierdzenia 3 kończy cały dowód. Reszta na tablicy.
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Wstęp Konstrukcja równoważnego DAS
Przedstawienie zagadnienia Tworzenie elementów definicji formalnej
Elementy tworzonego DAS skonstruowane są z podzbiorów
NAS są zazwyczaj łatwiejsze do zaprogramowania
stanów z NAS. A oto szczegóły:
Zaskakujące jest, że dla każdego NAS N istnieje DAS D,
QD = {S : S ą" QN} QD jest zbiorem podzbiorów QN, czyli
taki że L(D) = L(N), i odwrotnie
jest zbiorem potęgowym QN, a jego liczność wynosi
Dowód obejmuje tzw. konstrukcję podzbiorów i jest
|QD| = 2|QN|, lecz nie wszystkie elementy QD muszą być
przykładem na to jak w sposób typowy można
wykorzystane
skonstruować automat B z automatu A
Mając dany NAS FD = {S ą" QN : S )" FN = "} czyli te podzbiory, które

zawierają chociaż jeden stan końcowy z N
N = (QN, Ł, �N, q0, FN)
Dla każdego S ą" QN i a " Ł
Skonstruujemy DAS
�D(S, a) = �N(p, a)
D = (QD, Ł, �D, q0, FD)
p"S
taki, że
L(D) = L(N)
Alfabety wejściowe Ł są takie same, a stan początkowy w
i dowód tego ostatniego przeprowadzimy formalnie D to {q0}, gdzie q0 to stan początkowy w N
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Konstrukcja równoważnego DAS Konstrukcja równoważnego DAS
Przykład: tablica przejść równoważnego DAS Zbiory stanów z NAS to stany w DAS
Elementami tablicy dla D są zbiory stanów z N. Możemy nadać
NAS N
nowe nazwy tym zbiorom, np. kolejno od A do H i otrzymamy
"normalnie" wyglądający automat deterministyczny
�D 0 1
�D 0 1 �D 0 1
" " "
0,1
" " " A A A
{q0} {q0, q1} {q0}
Start
{q0} {q0, q1} {q0} B E B
{q1} " {q2}
q0 0 q1 1 q2
{q1} " {q2} C A D
{q2} " "
{q2} " " D A A
{q0, q1} {q0, q1} {q0, q2}
{q0, q1} {q0, q1} {q0, q2} E E F
{q0, q2} {q0, q1} {q0}
{q0, q2} {q0, q1} {q0} F E B
{q1, q2} " {q2}
{q1, q2} " {q2} G A D
{q0, q1, q2} {q0, q1} {q0, q2}
{q0, q1, q2} {q0, q1} {q0, q2} H E F
Automat N składa się z 3 stanów i 3 przejść
Zaczynając od stanu początkowego B osiągamy tylko stany B,
E i F . Pozostałe 5 stanów są nieosiągalne, i można je pominąć.
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Konstrukcja równoważnego DAS Twierdzenia i dowody
"Leniwe" obliczanie podzbiorów Twierdzenia o równoważności NAS i DAS
Jeżeli obliczenia pozycji tablicy przejść dla DAS zaczniemy
Twierdzenie (2.11)
od stanu początkowego i będziemy je kontynuować tylko
Jeżeli D = (QD, Ł, �D, q0, FD) jest DAS skonstruowanym z NAS
poprzez stany osiągalne to możemy uniknąć "eksplozji"
N = (QN, Ł, �N, q0, FN) za pomocą konstrukcji podzbiorów, to
stanów, co formalnie:
L(D) = N(D).
Podstawa: S = {q0} jest osiągalny w D
Krok indukcyjny: Jeżeli stan S jest osiągalny, wtedy dla
Dowód.
każdego symbolu wejściowego a obliczamy zbiór stanów
Dowodzimy indukcyjnie po długości |w|, że
�D(S, a) = �N(p, a)
Ć Ć
�D({q0}, w} = �N({q0}, w}
p"S
Ć
DAS D ze stanami osiągalnymi (3 stany, 6 przejść):
Obie funkcje � zwracają zbiory, lecz różnie je interpretują.
Ć
1 0
Podstawa: Niech w = , wówczas z definicji �
Start
0 1
Ć Ć
{q0} {q0, q1} {q0, q2}
�D({q0}, ) = �N({q0}, ) = {q0}
1 0
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Twierdzenia i dowody Twierdzenia i dowody
Twierdzenie o równoważności NAS i DAS Twierdzenia o równoważności NAS i DAS
Twierdzenie (2.12)
Dowód c.d.
Język L jest akceptowany przez jakiś DAS wtedy i tylko wtedy,
Ć Ć
Krok indukcyjny: Zakładamy, że �D({q0}, x) = �N(q0, x).
gdy L jest akceptowane przez jakiś NAS
Chcemy dowieść tej równości dla w = xa.
Ć Ć Ć
�D({q0}, xa) = �D(�D({q0}, x), a) z definicji �D
Dowód.
Ć
= �D(�N(q0, x), a) z założenia indukcyjnego
(<=) Wynikanie <= to konstrukcja podzbiorów z twierdz. 2.11
= �N(p, a) z konstrukcji podzbiorów
Ć
p"�N (q0,x)
Ć Ć (=>) Każdy DAS to NAS, który "przypadkiem" w każdej sytuacji
= �N(q0, xa) z definicji �N
ma tylko jedną możliwość przejścia. Musimy tylko
Po wczytaniu w DAS znajduje się w stanie będącym zbiorem
zmodyfikować funkcję przejścia wg reguły:
stanów NAS, w których NAS znajdowałby się po wczytaniu w.
Jeżeli NAS znajdowałby się w stanie akceptującym, to DAS ten
Jesli; �D(q, a) = p, to �N(q, a) = {p}
stan również zawiera, czyli L(D) = L(N).
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Zły przypadek konstrukcji podzbiorów Zły przypadek konstrukcji podzbiorów
Wykładniczy wzrost liczby stanów DAS DAS wykrywający 1 na 3 znaki od końca
NAS wykrywający 1 na 3 znaki od końca (4 stany, 4 przejścia):
Można podać przykład NAS o n + 1 stanch, dla którego nie
0,1
ma równoważnego DAS o mniej niż 2n.
Start
Ten NAS rozpoznaje napisy z 1 na n-tej pozycji od końca:
q0 1 q1 0,1 0,1
q2 q3
0,1
Start
Tabela przejść dla równoważnego DAS
q0 1 q1 0,1 0,1 " " " 0,1 0,1 qn
q2
�D 0 1
Co formalnie można zapisać: {q0} {q0} {q0, q1}
{q0, q1} {q0, q2} {q0, q1, q2}
L(N) = {x1c2c3 � � � cn : x " {0, 1}", ci " {0, 1}}
{q0, q2} {q0, q3} {q0, q1, q3}
{q0, q1, q2} {q0, q2, q3} {q0, q1, q2, q3}
{q0, q3} {q0} {q0, q1}
Dowód nieformalny: Intuicyjnie czujemy, że każdy stan z
{q0, q1, q3} {q0, q2} {q0, q1, q2}
DAS musi pamiętać kolejność 1 na n ostatnio wczytanych
{q0, q2, q3} {q0, q3} {q0, q1, q3}
pozcyjach, zatem musi być 2n stanów.
{q0, q1, q2, q3} {q0, q2, q3} {q0, q1, q2, q3}
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Zły przypadek konstrukcji podzbiorów Przeszukiwanie tekstu
Diagram stanów dla równoważnego DAS NAS znajdujacy łańcuchy w tekście
0 NAS rozpoznający wystąpienia słów web i ebay. Ł
0 reprezentuje zbiór znaków ASCI
Start
{q0} {q0,q3}
1
100
0
Ł
e
1 {q0,q2} 0 b
2 3 4
10
w
1 Start
{q0,q1,q3}
1
1 101
0
e
{q0,q1}
1
5 6 7 8
1
b a
0 y
1
{q0,q2,q3}
0
110
{q0,q1,q2}
0
11
Istnieją dwie opcje implementacyjne:
1
{q0,q1,q2,q3}
1
111
napisać program symulujący ten NAS poprzez ob liczanie
zbioru stanów następnych
DAS wykrywający 1 na 3 znaki od końca (8 stanów, 16 przejść).
zamienić ten NAS na DAS i następnie bezpośrednio
W stanach zaznaczono wszystkie wczytane 1 na ostatnich 3
zasymulować DAS
pozycjach.
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Przeszukiwanie tekstu Automaty z pustymi symbolami na wejściu
DAS rozpoznający zbiór słów kluczowych Automat skończony z epsilon-przejściami
Ł-a-e-w
Automat z -przejściami to taki automat, który może
q0 w NAS to {q0} w
w
Ł-b-e-w
zmieniać swój stan bez wczytywania symbolu z wejścia.
DAS
w
w -NAS akceptujący dziesiętne liczby rzeczywiste składa się
Ł-e-w jeżeli p " QN jest
e b kolejno z:
12 135 146
osiągany z q0 po ciągu
1
Opcjonalny znak + lub -
w a1a2 � � � am to do zbioru
w
2
Ciąg cyfr
stanów z DAS należą:
Ł-e-w 1 w a
3
Kropka dziesiętna
1
q0
e
e
4
Kolejny ciąg cyfr
2
e w w p
Start
e
3
Jeden z ciągów (2) lub (4) jest opcjonalny
b a y każdy stan z NAS
15 16 17 18
Ł-b-e-w
osiągalny z q0, 0,1,& ,9 0,1,& ,9
e
wzdłuż ścieżki, której
Start
Ł-a-e-w
e
etykiety są sufiksami q0 �,+,- q1 . q2 0,1,& ,9 q3 � q5
e
a1a2 � � � am, tzn.
Ł-e-w-y
0,1,& ,9 .
każdy ciąg postaci
q4
ajaj+1 � � � am
Ł-e-w
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Automaty z pustymi symbolami na wejściu Automaty z pustymi symbolami na wejściu
Inny przykład -NAS -NAS definicja formalna
-przejścia nie rozszerzają klasy języków akceptowanych przez
-NAS jest to uporządkowana piątka (Q, Ł, �, q0, F ) gdzie �
AS, lecz nieco zwiększają "wygodę programowania".
jest funkcją która odwzorowuje ze zbioru Q � Ł *" { } w
Uniwersalny -NAS szukającyc słów web i ebay
zbiór potęgowy Q. Uwaga: nie należy do Ł.
Przykład -NAS akceptującego dziesiętne liczby
Ł
w e b
1 2 3 4
rzeczywiste.
�
Start
9
E = ({q0, q1, q2, q3, q4, q5}, {., +, -, 0, 1, . . . , 9}, �, q0, {q5})
�
0 5 6 7 8
e b a
y
gdzie funkcja przejścia � jest następująca:
� +, - . 0, . . . , 9
Budujemy pełny ciąg stanów dla każdego słowa
q0 {q1} {q1} " "
kluczowego, jak gdyby było ono jedynym słowem, które
q1 " " {q2} {q1, q4}
automat rozpoznaje.
q2 " " " {q3}
Następnie dodajemy nowy stan początkowy (stan nr 9) z
q3 {q5} " " {q3}
-przejściami do stanów automatu dla każdego ze słów
q4 " " {q3} "
kluczowych.
q5 " " " "
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Automaty z pustymi symbolami na wejściu Automaty z pustymi symbolami na wejściu
-domknięcia Przykład -domknięcia
Nieformalnie
-domykamy stan q idąc po wszystkich przejściach ze
stanu q opatrzonych etykietą . Gdy dojdziemy do jakiegoś
� �
2
stanu, dalej podążamy z niego po przejściach z etykietą , 3 6
o ile takie istnieją. -domknięciem stanu q jest zbiór tych �
1 b
wszystkich stanów, do których możemy dojść z q po
etykietach . �
4 5 7
Formalnie
a �
Podstawa: Stan q należy doEDOMK(q).
Krok indukcyjny: Jeżeli stan p należy doEDOMK(q) oraz
EDOMK(1) = {1, 2, 3, 4, 6}
istnieje przejście ze stanu p do r o etykiecie , to r należy
doEDOMK(q). Lub bardziej precyzyjnie dla każdego �(p, ):
p "EDOMK(q) �! �(p, ) "EDOMK(q)
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Automaty z pustymi symbolami na wejściu Automaty z pustymi symbolami na wejściu
Ć
Eliminacja -przejść
Rozszerzona funkcja przejścia � dla -NAS
Ć
W zamierzeniu �(q, w) jest zbiorem stanów osiągalnych po
ścieżce, której etykiety po złożeniu tworzą ciąg w. Etykiety
Dla danego -NAS E można znlez
ć DAS D, który
na ścieżce nic nie wnoszą do w.
akceptuje ten sam język co E.
Ć
Podstawa: �(q, ) =EDOMK(q).
Niech E = (QE, Ł, �E, q0, FE). Wtedy równoważny DAS:
Ć
Krok indukcyjny: Załóżmy że w = xa. Wartość �(q, w)
obliczamy następująco:
D = (QD, Ł, �D, qD, FD)
Ć
1
Niech �(q, x) = {p1, p2, . . . , pk}, czyli to są te stany do
których można dojść z q po etykiecie x.
jest zdefiniowany następująco:
k
2
Niech �(pi, a) = {r1, r2, . . . , rm}. Stany rj to niektóre ze
1
i=1
QD jest zbiorem podzbiorów QE, a dokładniej wszystkie
stanów, do których możemy dojść z q po etykiecie w.
stany D są -domkniętymi podzbiorami QE, tj. zbiorami
Brakuje tylko -domknięć stanów rj.
S ą" QE takimi, że S =EDOMK(S).
m
Ć
3
Zatem: �(q, w) = EDOMK(rj). 2
qD =EDOMK(q0).
i=1
3
Bardziej formalnie:
FD = {S | S " QD oraz S )" FE = "}.

4
�D(S, a) = {EDOMK(p) : p " �(t, a) dla wszystkich t " S}.
Ć
�(q, xa) = EDOMK(p)
Ć
p"�(�(q,x),a)
Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS Wprowadzenie DAS NAS Równoważność DAS i NAS Zastosowanie -NAS
Automaty z pustymi symbolami na wejściu Automaty z pustymi symbolami na wejściu
Przykład: -NAS z liczbami rzeczywistymi i jego DAS Twierdzenie o językach -NAS i DAS
0,1,& ,9 0,1,& ,9
Start
q0 �,+,- q1 . q2 0,1,& ,9 q3 � q5
Twierdzenie (2.22)
0,1,& ,9 .
q4
Język L jest akceptowany przez pewien -NAS wtedy i tylko
wtedy, gdy L jest akceptowany przez pewien DAS.
0,1,& ,9 0
Start
+,- .
Dowód.
{q0,q1} {q1} {q1,q4} {q2,q3,q5}
0,1,& ,9
. 0,1,& ,9
.
{q2} {q3,q5}
0,1,& ,9
0,1,& ,9