PodstawyTeorii Automató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 aibi 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,
L4  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óz
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 xuviwz 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ędz
zawierającą
dany symbol x otoczony okręgiem.
Każde wystąpienie symbolu nieterminalnego A w napisie ai^ jest oznacza się przez krawędz

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 wzwR czyli takie, że na początku
dowolna ilośd symboli ,a, b-, póz
niej symbol z i póz
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:


Symbole terminalne pisze się w BNF bez żadnych zaznaczeo.
Symbol ::= (czyt.  jest równe z definicji ) łączy strony produkcji.
Przykład:
::=
Symbol | oznacza w produkcjach spójnik logiczny lub.
Przykład:
::= |
Minijęzyk:
::= program

begin

end;
::= |
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:
--> w^
gdzie w^ {Vt Va}*, A Va.
(używane do opisów języków programowania)
Vt={a,b}
Va={}
R={ --> aI,
-->bb,
--> aa,
--> bb}
3:
Reguły wyprowadzeo mają postad:
--> a
--> a albo --> a
gdzie a Vt, , Va.
Jedna gramatyka może mied tylko reguły (wyprowadzenia) lewostronne, lub też tylko reguły
(wyprowadzenia) prawostronne.
Gramatyka prawostronna:
Vt={a,b}, Va={, , }
R={ --> a, -->a, --> b,
--> b, --> $},
Gramatyka lewostronna:
Vt={a,b}, Va={, , }
R={ --> b, --> a, --> a,
--> a, --> $}.
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 Ś(n3) 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)