P TA
odstawy
eorii
utomatów
1. NAS, DAS, definicje, różnice
Automat skooczony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach.
i i
AS nie można na nim zrobid a b bo automat skooczony nie umie liczyd.
NAS- niedeterministyczny automat skooczony – to maszyna o skooczonej liczbie stanów, która
zaczynając w stanie początkowym czyta kolejne symbole słowa. Po przeczytaniu symbolu zmienia stan
na stan będący elementem zbioru (stanów), który jest wartością funkcji przejścia. Jeśli po przeczytaniu
słowa znajdujemy się w stanie akceptującym, czyli automat akceptuje dane słowo. NAS definiujemy
jako (Q,∑,δ,q0,F)
Q- skooczony zbiór stanów
∑ - skooczony alfabet wejściowy
δ – funkcja przejśd
q0 – stan początkowy
F – zbiór stanów akceptujących
DAS – deterministyczny automat skooczony – maszyna o skooczonej liczbie stanów, która zaczynając w
stanie początkowym czyta kolejne symbole słowa. Po przeczytaniu symbolu zmienia stan na będący
wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu słowa
znajdujemy się w stanie akceptującym, czyli słowo należy do języka regularnego, do rozpoznawania
którego jest zbudowany DAS. DAS definiujemy jako (∑,Q,q0,F, δ) przyjmując że symbole znaczą to
samo co w NAS.
Czyli DAS to taki ze z jednego stanu możesz po danej zmiennej alfabetu przejśd tylko do jednego stanu,
a w NAS może byd tak że są dwie lub więcej dróg.
Twierdzenia o równoważności automatów NAS i DAS:
-Każdy DAS jest NAS.
-Dla każdego NAS można zbudowad równoważny z nim DAS.
-Wniosek: NAS akceptuje tylko klasę języków regularnych.
2. Automaty z wyjściem: Mealy'ego i Moore'a
Automaty skooczone z wyjściem – wartośd wyjścia jest wybierana z innego alfabetu niż „akceptuję/nie
akceptuję”.
-wyjście może byd związane z aktualnym stanem (automat Moore’a)
-wyjście może byd związane z przejściem (automat Mealy’ego)
Automat Moore’a jest oczywiście typu DAS i jest uporządkowaną szóstką (∑,Q, ∆, δ, λ,q0) ∆-alfabet
wyjściowy, λ – funkcja wyjścia, zależy tylko od stanu w którym znajduje się automat.
Automat Mealy’ego opisujemy taką samą szóstką z tym, że λ (funkcja wyjśd) – zależy od stanu w
którym znajduje się automat oraz od sygnału wejściowego.
3. Wszystkie konwersje na automaty równoważne
Z dwiczeo…
4. E-przejścia i E-domknięcia, do czego służą
ε – przejścia to w NAS przejście na kolejny stan bez podania znaku na wejściu
ε – domknięcie – zbiór wszystkich wierzchołków takich, że istnieje droga z q do p o etykiecie ε
oznaczamy przez ε- DOMKN(q)
Służą do zamiany NAS na DAS tj. jak na dwiczeniach E-NAS na DAS.
5. wyrażenia regularne, symbolika, klasy znaków
L={A-Z, a-z} oznacza litery
C={0-9} oznacza cyfry
L C – zbior liter i cyfr
LC – zbiór napisów składających się z litery i występującej po niej cyfrze,
4
L – zbiór wszystkich napisów czteroliterowych
L* - zbiór wszystkich napisów złożonych z liter
+
C - zbiór wszystkich napisów złożonych co najmniej z jednej cyfry
L(LuC)* - zbiór napisów składających się z
(…)
… np: ABC
α i β zbiór terminali i nieterminali (mogą byd puste)
γ – zbiór terminali i nieterminali
Gramatyka bezkontekstowa – A->T gdzie A jest nieterminalnym, a T jest dowolnym zbiorem symboli
terminalnych i nieterminalnych (może byd pusty)
Gramatyki ogólne – to jest tak że po lewej stronie strzałki zawsze jeden symbol nieterminalny i teraz
mogą byd te gramatyki prawostronne lub lewostronne tj…
…,+,(,)}
Poprawne wyrażenia:
v+v+v
v+(v+v)
(v+v)+(v+v)
Niepoprawne wyrażenia:
v+v+
(v+v)(v+v)
10.notacja BNF (i EBNF)
Notacja Backusa-Naura (BNF)
Używana przy opisie składni konkretnych języków programowania ze względu na swoją przejrzystośd.
Jest to system zapisywania produkcji gramatyk.
Symbole nieterminalne, służące do nazywania jednostek składniowych definiowanego języka
umieszcza się w nawiasach kątowych…
… ...
[ else
instrukcja ... ]
end if;
liczba_całkowita :: == cyfra ...
identyfikator ::= litera [ [ ] litera] ...
instrukcja_wejścia ::= input identyfikator
[, identyfikator] ... ;
11.Maszyna Turinga, Uniwersalna Maszyna Turinga
Maszyną Turinga nazywamy (Q, Σ, Γ, δ, q0, B, F), gdzie
Język akceptowany to taki, że po umieszczeniu na taśmie dowolnego słowa automat znajdzie się w
stanie koocowym.
MT – urządzenie…
….
• Charakterystyka maszyny nie zależy od szczegółów typu ile symboli jest danych itp.
• Nie istnieje maszyna Turinga, która, gdy ma opis jakiejś maszyny Turinga i jej dane wejściowe,
zatrzyma się, jeśli przy tych samych danych wejściowych zatrzyma się opisywana maszyna.
Uniwersalna maszyna Turinga:
•
•
Maszyna, która potrafi udawad dowolną inną maszynę Turinga,
Na początku taśmy ma zakodowaną listę instrukcji…
… na wyrażenia regularne – najpierw na ε-NAS, a później na DAS
7. gramatyki, lemat o pompowaniu, bezkontekstowe, kontekstowe,
ogóle, wyrażenia regularne
Lemat o pompowaniu – Niech A będzie językiem regularnym. Wówczas istnieje takie k, że dla
dowolnych słów x,y i z takich, że xyz należy do A oraz |y|>=k, można y podzielid na słowa u, v i w,
i
y=uvw w taki sposób, że v!= epsilon (nie jest puste…
... zobacz całą notatkę
Komentarze użytkowników (0)