P

odstawy

T

eorii

A

utomatów

1. NAS, DAS, definicje, różnice

Automat skooczony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach.

AS nie można na nim zrobid a

i

b

i

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,

L

4

– 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 liter lub cyfr, zaczynających się od litery

Wyrażenie regularne to notacja pozwalająca na definiowanie takich zbiorów jak L(L | C)*

Wyrażenie regularne jest budowane z prostszych wyrażeo regularnych przy użyciu zestawu reguł
definiowania, każde wyrażenie regularne r definiuje język L(r)

Priorytety w wyrażeniach regularnych:

- operator * ma najwyższy priorytet i jest lewostronnie łączny

-złączenie ma drugi priorytet i jest lewostronnie łączne

-alternacja | ma najmniejszy priorytet i jest lewostronnie łączna

Np.: (a)|((b)*(c)) można zapisad jako a|b*c

Równoważnośd wyrażeo regularnych: jeżeli dwa wyrażenia regularne opisuja ten sam język to są
równoważne.

*- występuje 0 lub więcej razy

+ - występuje 1 lub wiecej razy

? – występuje 0 lub 1 razy

Tu jakieś gówno się pojawia czyli: równoważnośd AS z WR

NAS->DAS->WR->NAS z e-przejściami->NAS->DAS->WR->i tak w kółko

Twierdzenie: niech r będzie WR, wtedy istnieje NAS z E-przejściami, który akceptuje L(r).

6. konwersje (Thompsona, DAS na wyrażenia regularne)

Thompson – na dwiczeniach to takie że były zdefiniowane R+E, RE, R*
DAS 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,
y=uvw w taki sposób, że v!= epsilon (nie jest puste) i dla wszystkich i>=0 xuv

i

wz należy do A

Czyli generalnie jest sobie słowo xyz i teraz to polega na tym ze z y robimy jakby nowe slowo które
jest uvw i teraz u i w musza wystąpid 1x a v ile se chce ;p

Gramatyka kontekstowa αAβ -> αγβ i tutaj A jest zastępowane przez γ, a otaczaja ją αβ więc to jest
kontekst, stąd gramatyka kontekstowa – CHYBA :D

Terminale – czyli symbole koocowe np.: a,b,c

Nieterminale – czyli zmienne 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: i teraz dla lewostronnej (po prawej stronie
strzałki) występuje jeden symbol nieterminalny i jest on skrajnie po lewej, a dla prawostronnej tak
samo tylko jest on po prawej :D

Gramatyki ogólne – nie posiadają żadnych ograniczeo na reguły generowania

8. drzewo składniowe, wykres składniowy, opis składniowy

Opis składniowy – wyprowadzenie określonego łaocucha z danej gramatyki, czyli jak się buduje
wyrażenia w danej gramatyce, zasady budowy, np.: A-->a1^a2^…an^

Drzewa składniowe (inaczej: drzewa wyprowadzenia, drzewa rozkładu) są używane do przedstawiania
wyprowadzenia określonego łaocucha z danej gramatyki bezkontekstowej.

Wykresy składniowe, diagramy syntaktyczne:
Użycie wykresu składniowego zwiększa czytelnośd zapisu i ułatwia zrozumienie złożonych opisów
składniowych. Z ich pomocą zdefiniowano składnię Pascala (1973 r.) oraz Fortrana (1978 r.).

Każde wystąpienie symbolu terminalnego x w napisie ai^ jest oznacza się przez krawędź zawierającą
dany symbol x otoczony okręgiem.

Każde wystąpienie symbolu nieterminalnego A w napisie ai^ jest oznacza się przez krawędź
zawierającą dany symbol A otoczony prostokątem.

Przykład dla mini języka jakiegoś tam:

9. automaty ze stosem

Automat ze stosem to automat skooczony z dodatkowym urządzeniem do zapamiętywania danych -
stosem (ang. stack).
W przeciwieostwie do przykładów, na stos są odkładane symbole, a nie kolorowe elementy.
Zasady pracy ze stosem:

•

symbole są umieszczane wyłącznie na szczycie stosu (operacja PUSH),

•

tylko symbol na szczycie stosu może zostad odczytany,

•

tylko symbol na szczycie stosu może zostad usunięty (operacja POP).

Definicja:
Automat skooczony ze stosem jest siódemką uporządkowaną (Q, Σ, Γ, δ, q0, Z0, F),
gdzie

Automaty ze stosem akceptują wyrażenia wygenerowane z gramatyk bezkontekstowych.

Konfiguracja automatu ze stosem jest trójką
< s, x, w > gdzie
s jest stanem,
x jest łaocuchem alfabetu wejściowego,
w jest łaocuchem alfabetu stosowego.

ogólnie chodzi o to że się poruszamy bo ciągu i dorzucamy na stos lub odejmujemy z niego i jeśli
zostanie lub jest za mało na koocu to nie zaakceptowaliśmy, lub jeśli chcemy zrzucid inny kolor

przykładowo mamy ciąg aabb
to jak a to wrzucamy na stos jak b zrzucamy czyli po kolei będzie:
0 – wrzucamy (bo a)
1 – wrzucamy (bo a)
2 – zrzucamy (bo b)

1 – zrzucamy (bo b)
0 – nie ma nic więcej w ciągu i na stosie czyli jest zaakceptowany

ciąg aaabb:
0 – wrzucamy (bo a)
1 – wrzucamy (bo a)
2 – wrzucamy (bo a)
3 – zrzucamy (bo b)
2 – zrzucamy (bo b)
1 – nie ma nic więcej w ciągu a mamy coś na stosie czyli nie jest zaakceptowany

Przykład dla ciągu abazaaa (ma byd wykrywanie czy ciągi są w rodzaju wzw

R

czyli takie, że na początku

dowolna ilośd symboli ,a, b-, później symbol z i później to co na początku w odwrotnej kolejności, dla a
odkładamy czerwone, dla b niebieskie, po z zdejmujemy

Przykładowo (akceptacja prostych wyrażeo):
Vt={v,+,(,)}

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.
Przykład:
<lista>
<element_listy>

Symbole terminalne pisze się w BNF bez żadnych zaznaczeo.

Symbol ::= (czyt. „jest równe z definicji”) łączy strony produkcji.

Przykład:
<lista> ::= <element_listy><lista>
Symbol | oznacza w produkcjach spójnik logiczny lub.
Przykład:
<lista> ::= <element_listy><lista>|<element_listy>

Minijęzyk:
<program> ::=

program

<ciąg-deklaracji>

begin

<ciąg-instukcji>

end;

<ciąg_deklaracji> ::= <deklaracja>|<deklaracja><ciąg_deklaracji>


Notacja EBNF:
(ang. Extended Backus-Naur Form) jest to notacja BNF rozszerzona o następujące symbole

•

nawiasy [a+ oznaczające co najwyżej jednokrotne wystąpienie napisu a,

•

nawiasy {a- oznaczające, że napis a może wystąpid dowolnie wiele razy po sobie,

•

+ po symbolu a (lub po nawiasach *+, ,-) oznacza, że symbol lub napis może wystąpid dowolną
niepustą liczbę razy,

•

* lub ... po symbolu a lub nawiasach *+, ,- oznacza, że symbol lub napis można powtórzyd dowolną
liczbę razy (także zero).

•

Liczbowe oznaczenia dopuszczalnych krotności występowania symboli pisze się w postaci dolnych
i górnych indeksów.

•

Symbole nieterminalne pisze się niekiedy bez nawiasów <>, ale inną czcionką (np. kursywą).

instrukcja_jeśli ::= if porównanie then

instrukcja ...

[ 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 obliczające funkcje na liczbach całkowitych

•

MT można traktowad jak urządzenie akceptujące języki

•

MT można traktowad jako urządzenie obliczające funkcje z liczb całkowitych w liczby całkowite.

•

Do zapisu argumentów i wyniku – system jedynkowy.

•

Jeżeli MT zatrzymuje się z taśmą zawierającą 1m dla pewnego m, to mówimy, że f(i1,i2,….,ik)=m,
gdzie f jest funkcją o k argumentach obliczaną przez tę MT.

•

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 dla dowolnej MT. (w formie np. R -> 1110)

12. Teza Churcha-Turinga

Intuicyjne pojęcie funkcji obliczalnej może byd utożsamiane z klasą funkcji częściowo rekurencyjnych.
Funkcje częściowo rekurencyjne generują MT, maszyna RAM, rachunek λ, systemy Posta, uogólnione
funkcje rekurencyjne.

13. hierarchia Chomsky’ego, postad naturalna Chomsky’ego

Hierarchia Chomsky’ego:
0 - gramatyki ogólnego rodzaju,
1 - gramatyki kontekstowe,
2 - gramatyki bezkontekstowe,
3 - gramatyki regularne.

0:
Nie posiadają żadnych ograniczeo na reguły generowania.
Dowolna reguła r=F’-->F’’ może byd utworzona przez wykorzystanie łaocuchów ze zbioru
(Vt Va)*.

W gramatyce 0 jedna reguła może od razu zmienid kilka symboli.

1:
Reguły wyprowadzeo mają postad:
t1 A t2 --> t1 w^ t2
gdzie t1,t2,w^ {Vt Va}*, A Va.
Wyrazy t1 i t2 nie ulegają zmianom przy stosowaniu reguły,
dlatego nazywamy je kontekstem
(t1 - lewy kontekst, t2 - prawy kontekst).

Vt={a,b,c,d}
Va={I, A, B}
R={I --> aAI,
AI-->AA,

(niepusty lewy kontekst)

I --> ABA

A-->b,
bBA-->bcdA,

(zawiera oba konteksty)

bI-->ba}.

(niepusty lewy kontekst)

2:

Reguły wyprowadzeo mają postad:
<A> --> w^
gdzie w^ {Vt Va}*, A Va.
(używane do opisów języków programowania)
Vt={a,b}
Va={<I>}
R={<I> --> aI,
<I>-->b<I>b,
<I> --> aa,

<I> --> bb}

3:
Reguły wyprowadzeo mają postad:
<A> --> a
<A> --> a<B> albo <A> --> <B>a
gdzie a Vt, <A>,<B> Va.
Jedna gramatyka może mied tylko reguły (wyprowadzenia) lewostronne, lub też tylko reguły
(wyprowadzenia) prawostronne.

Gramatyka prawostronna:
Vt={a,b}, Va={<I>, <A>, <Z>}
R={<I> --> a<I>, <I>-->a<A>, <A> --> b<A>,
<A> --> b<Z>,<Z> --> $},
Gramatyka lewostronna:
Vt={a,b}, Va={<I>, <A>, <Z>}
R={<I> --> <A>b, <A> --> <A>a, <A> --> <Z>a,
<Z> --> <Z>a,<Z> --> $}.

Zastosowanie Postaci Normalnej Chomsky’ego:

•

CNF jest ważną formą gramatyki bezkontekstowej, ponieważ algorytmy wykorzystujące CNF są
często efektywniejsze.

•

Przykładowo algorytm CYK (Cocke-Younger-Kasami) określający, czy dany ciąg jest generowany
przez daną gramatykę CNF ma złożonośd Θ(n

3

) jest najszybszym algorytmem tego typu.

14. problemy nierozstrzygalne,

Problem decyzyjny jest rozstrzygalny (ang. decidable, solvable) jeżeli istnieje algorytm, który dla dowolnych
danych udzieli poprawnej odpowiedzi.

Przykłady problemów nierozstrzygalnych:

•

Problem stopu (ang. halting problem)

– Czy maszyna M zatrzyma się na łaocuchu w?

•

Problem należenia (ang. membership problem)

– Czy maszyna M akceptuje łaocuch w?

•

Problem stopu przy pustej taśmie (ang. blank-tape halting problem)

– Czy maszyna M zatrzyma się przy pustym łaocuchu?

•

Problem wejścia do stanu (ang. state-entry problem)

– Czy maszyna M wejdzie do stanu q przy łaocuchu w?

Przykłady dla języków rekurencyjnie nieprzeliczalnych:

•

Czy L jest puste?

•

Czy L jest skooczone?

•

Czy L zawiera dwa różne łaocuchy o tej samej długości?

15. języki rekurencyjne, przeliczalne, częściowo rekurencyjne funkcje

Funkcja jest nieobliczalna, jeżeli nie może zostad wyliczona dla wszystkich elementów ze swojej
dziedziny.
Dowolny język wygenerowany przez gramatykę nieograniczoną jest rekurencyjnie przeliczalny.
Język rekurencyjny – maszyna Turinga, która się zatrzymuje
język rekurencyjny przeliczalny – maszyna Turinga

Języki rekurencyjnie przeliczalne – języki akceptowane przez MT, istnieją języki dla których automat
wejdzie w obliczenia nieskooczone
języki rekurencyjne – podklasa JRP, są akceptowane przez przynajmniej jedną MT, zatrzymanie nie
musi byd koniecznie poprzedzone akceptacją.
funkcje częściowo rekurencyjne - to takie funkcje, które dla pewnych danych wejściowych wejdą w
obliczenia nieskooczone
funkcje całkowicie rekurencyjne – to takie funkcje, które zawsze się zatrzymują, niezależnie od
wejściowych danych

16. system jedynkowy

jak w więzieniu:
I oznacza 1
II oznacza 2
III oznacza 3
IIII oznacza 4
IIIII oznacza 5
IIIII… itd.
nie nadaje się do kodowania dużych liczb (I to oczywiście dla nas 1)
większe liczby można kodowad w sposób wykorzystujący zera:
011011110 – oznacza 24 w Dec, ponieważ zera oddzielają cyfry
01110011111110 – oznacza 307 w Dec (dwa zera to 0)