I wykład - automat Moore`a, Mealy`ego - przejścia

Informatyka to usystematyzowana wiedza na temat obliczania.

Główne składowe informatyki - fundamentalne (teoretyczne) - idee i modele leżące u podstaw obliczania; techniki inżynieryjne używane przy projektowaniu systemów obliczeniowych.

Źródła informatyki teoretycznej - matematyka(logika matematyczna), elektryka(teoria przełączników), biologia(sieci neuronowe), lingwistyka(gramatyka języków naturalnych).

Automat skończony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach.

łańcuch/słowo - skończony ciąg zestawionych razem symboli,

długość łańcucha w (|w|) - liczba symboli tworzących łańcuch w,

łańcuch pusty (ε) - składa się z zera symboli: | ε |=0

przedrostek łańcucha - dowolna liczba symboli rozpoczynających łańcuch,

przyrostek łańcucha - dowolna liczba symboli kończących łańcuch,

alfabet - skończony zbiór symboli,

język (formalny) - zbiór łańcuchów złożonych z symboli jednego alfabetu.

Operacja konkatenacji(złożenia) - złożenie dwóch łańcuchów v, w(vw).E(epsylon) jest neutralnym elementem konkatenacji.

Automat skończony - piątka uporządkowana(Q, , δ, q0, F),

Q - skończony zbiór stanów.

 - skończony alfabet wejściowy.

q₀  Q - stan początkowy.

F  Q - zbiór stanów końcowych.

δQx>Q - funkcja przejścia.

Skończone sterowanie -­­­ układ o skończonej liczbie stanów, znajdujący się w stanie q ze zbioru Q.

Język nazywamy regularnym, jeżeli jest on językiem akceptowanym przez jakikolwiek automat skończony.

Automaty skończone z wyjściem - automat Moore`a(wyjście może być związane z aktualnym stanem), automat Mealy`ego(wyjście może być związane z przejściem).

Automat Moore'a jest uporządkowaną szóstką (Q,  , δ, (alfabet wyjściowy, (funkcja wyjścia(Q>),q0); jest skończony, gdy  = {0,1} i (q)=1.

Automat Mealy'ego jest uporządkowaną szóstką (Q,  ,  , δ , (Qx> ,q0).

Wyklad2: NAS->DAS + przejścia

NAS - Automat skończony, w którym dopuszczone jest istnienie zera, jednego lub więcej
przejść ze stanu przy tym samym symbolu wejściowym.

Q - skończony zbiór stanów

 - skończony alfabet wejściowy,

q0 - stan początkowy,

F c Q - zbiór stanów końcowych,

δ: Qx->2^Q - funkcja przejścia.

Każdy DAS jest NAS.

Dla każdego NAS można zbudować równoważny z nim DAS.

Wniosek: NAS akceptuje tylko klasę języków regularnych.

NAS M=(Q, , δ, q0, F) w DAS M'=(Q', , δ', q0', F')

2^Q - zbiór potęgowy Q (wszystkich podzbiorów Q)

AS z ε-ruchami - Rozszerzenie modelu NAS poprzez dołączenie przejść przy pustym wejściu ε.

ε-domknięcie - Zbiór wszystkich wierzchołków takich, że istnieje droga z q do p o etykiecie ε oznaczamy przez ε-DOMKN(q).

Jeżeli L(język) jest akceptowany przez NAS z ε-przejściami, to L jest akceptowany przez NAS bez ε-przejść.

III Wykład

Operacje na językach

suma L i M - L  M

Złączenie L i M - LM

Domknięcie L - L*

Dodatnie domknięcie - L⁺

definicja rekurencyjna

wyrażenie regularne jest budowane z prostszych wyrażeń regularnych przy użyciu zestawu reguł definiowania,

każde wyrażenie regularne r definiuje język L(r).

 jest WR reprezentującym zbiór pusty,

ε jest WR oznaczającym {ε},

jeśli a jest symbolem z S, to a jest WR oznaczającym {a},

Niech r i s - wyrażenia regularne oznaczające języki L(r) i L(s). Wtedy:

(r) | (s) - wyrażenie regularne oznaczające L(r) È L(s)

(r)(s) - wyrażenie regularne oznaczające L(r)L(s)

(r)* - wyrażenie regularne oznaczające (L(r))*

(r) - wyrażenie regularne oznaczające L(r)

Priorytety WR

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.

Równoważność wyrażeń regularnych:

Jeżeli dwa wyrażenia regularne r i s opisują

ten sam język, to są równoważne.

Zapis: r = s

Przykład: (a|b)=(b|a)

Niech r będzie WR. Wtedy istnieje NAS z ε-przejściami, który akceptuje L(r).

Jeżeli L jest akceptowane przez DAS,to L jest reprezentowany przez WR.

R^k_ij - zbiór łańcuchów przeprowadzających automat ze stanu qi w stan qj bez przechodzenia przez stan o numerze wyższym od k.

Trzy główne cnoty programisty to … … Lenistwo, Niecierpliwość i Pycha.

PERL

• Perl jest interpretatorem, ale cały skrypt jest najpierw sprawdzany, a dopiero później wykonywany,

• Zmienne muszą mieć przedrostek $.

• Perl może odczytywać ze standardowego wejścia (STDIN) lub z dowolnego pliku,

• By czytać ze STDIN, używa się uchwytu <STDIN>,

• Dane odczytane przez <STDIN> są umieszczane w zmiennej $_ .

• Polecenie open jest używanie do utworzenia uchwytu pliku dla pliku lub potoku.

• Nazwa uchwytu powinna być pisana dużymi literami (konwencja).

IV wykład - minimalizacja, długie wyrazy

Lemat o pomopowaniu -wszystkie wystarczająco długie słowa pozwalają na „pompowanie” podsłowa, nieformalnie(jeżeli język nie ma tej właściwości, jest nieregularny), formalnie(jeżeli „L” jest językiem regularnym, to istnieje stała „n” taka, że każde słowo „w” z „L” dłuższe niż „n” może być przedstawione jako w=xyz).

Flex - narzędzie do generowania skanerów, program, który rozpoznaje wzory leksykalne w tekście na podstawie opisu skanera.

Opis - formuła składająca się z par wyrażeń regularnych i kodu C, zwanych regułami.

Zasada działania Flexa - uruchomiony skaner analizuje swoje wejścia szukając wyrażeń regularnych, w momencie gdy napotka jakieś to wykonuje kod C odpowiedni dla danego wyrażenia, tekst, który nie odpowiada wzorcowi flexa kopiowany jest na wyjście.

Skaner - definicja tokenów, reguł i kod użytkownika.

Tokeny - przydatne w definicji wyrażeń regularnych.

Reguła - wzorzec(definiowany z wykorzystaniem wyrażeń regularnych i zdefiniowanych wcześniej tokenów), akcja(ujęty w nawiasach kod w C).

Kod użytkownika - dodatkowy kod dla niektórych funkcji.

V wykład - gramatyka

Formalna gramatyka generatywna: G={Vt, Va, IєVa, R},Vt - alfabet terminalny, Va - alfabet nieterminalny, I - symbol początkowy gramatyki, R - zbiór rodzaju f^→p^, (f^ i p^ - wyrazy).

Wyraz u^ bezpośrednio wyprowadzalny z w^:

1. r = f^→p^

2. w^ = t'f^t''

Gdzie t' , t'' є (VtυVa)

Wyraz u^=t'p^t'' może być utworzony z wyrazu w^ przez stosowanie reguły 1.

w^ ==> u^

Jeżeli zadany jest całokształt napisów w=(w0,w1,...,wn) takich, że istnieje ciąg wyprowadzeń bezpośrednich w0^==>w1^, w1^==>w2,... , wn-1^==>wn^, to taki ciąg nazywamy wyprowadzeniem wn^ z w0^ i oznaczamy w0^*=wn^.

Językiem generowny przez gramatykę G (L(G)) - zbiór wyrazów skończonych alfabetu terminalnego Vt gramatyki G, wyprowadzalnych z symbolu początkowego I.

L(G) = {w^ є Vt*|I*=>w^}

Pusty język - język generowany przez gramatykę G nie zawierający ani jednego wyrazu skończonego.

W teorii języków formalnych są cztery rodzaje gramatyk: 0-gramatyki ogólnego rodzaju, 1-gramatyki kontekstowe, 2-gramatyki bezkontekstowe, 3-gramatyki regularne.

Gramatyki ogólnego rodzaju - nie posiadają żadnych ograniczeń na reguły generowania; Dowolna reguła r=F'-->F'' może być utworzona przez wykorzystanie łańcuchów ze zbioru
(VtυVa)*; W gramatyce 0 jedna reguła może od razu zmienić kilka symboli.()

Gramatyki kontekstowe - reguły wyprowadzeń mają postać: 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).

Gramatyki bezkontekstowe (B) - reguły wyprowadzeń mają postać: <A> --> w^, gdzie w^ є {VtυVa}*, A є Va.

(używane do opisów języków programowania)

Gramatyki regularne (R) - reguły wyprowadzeń mają postać:

<A> --> a

<A> --> a<B> albo <A> --> <B>a

gdzie a є Vt, <A>,<B> є Va.

Jedna gramatyka może mieć tylko reguły (wyprowadzenia) lewostronne, lub też tylko reguły (wyprowadzenia) prawostronne.

Drzewa składniowe są używane do przedstawiania wyprowadzenia określonego łańcucha z danej gramatyki bezkontekstowej.

Wyprowadzenie napisu za pomocą reguł gramatyki może być zadane również za pomocą podania ciągów numerów porządkowych wykorzystanych reguł.

Jeżeli w trakcie budowy wyprowadzenia powstają napisy pośrednie zawierające kilka symboli nieterminalnych, to można kontynuować wyprowadzenie zmieniając którykolwiek z nich.
Jeden wyraz można więc wyprowadzić z danej gramatyki na więcej niż 1 sposób.

Jeżeli w każdym kroku stosujemy produkcję do zmiennej leżącej najbardziej na lewo (prawo), to wyprowadzenie to nazywamy lewostronnym (prawostronnym).

Każdemu drzewu składniowemu odpowiada dokładnie jedno wyprowadzenie lewostronne i dokładnie jedno wyprowadzenie prawostronne.

Napis języka L(G) jest niejednoznaczny, jeśli dla jego wyprowadzenia istnieje więcej niż jedno drzewo składniowe. Gramatyka niejednoznaczna - gdy gramatyka G tworzy napis niejednoznaczny.

Napisowi wyprowadzonemu w gramatyce może odpowiadać więcej niż jedno drzewo składniowe; drzewu składniowemu może odpowiadać więcej niż jedno wyprowadzenie (ale jedno prawo- i jedno lewostronne); jeden język może zostać uzyskany za pomocą różnych gramatyk (takie gramatyki nazywamy gramatykami równoważnymi).

Najpopularniejsze formy opisu gramatyk: symboliczna (używana dotychczas w przykładach), notacja Backusa-Naura (BNF, system zapisywania produkcji gramatyki. Ze względu na przejrzystość używana przy opisie składni konkretnych języków programowania, rozszerzona notacja Backusa-Naura (EBNF), postać iteracyjna, wykresy składniowe.

Symbole nieterminalne służą do nazywania jednostek składniowych definiowanego języka (umieszcza się w nawiasach kątowych, niekiedy bez nawiasów, ale inna czcionką, np. kursywą).

Symbole terminalne pisze się w BNF bez żadnych zaznaczeń.

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

Symbol | oznacza w produkcjach spójnik logiczny lub.

Notacja EBNF (Extended Backus-Naur Form) jest to notacja BNF rozszerzona o symbole:

• nawiasy [a], nawiasy {a}, a+, a*.

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

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

VI wykład - automat ze stosem

AZS->automat ze stosem

Automat ze stosem-automat skończony z dodatkowym urządzeniem do zapamiętywania danych - stosem. AZS akceptują wyrażenia wygenerowane z gramatyk bezkontekstowych.

Założenia AZS: głowica przesuwa się w każdym kroku,elementy odkładamy na szczyt stosu,pusty stos akceptacja ciągu.

Zasady: symbole są umieszczane tylko na szczycie stosu (PUSH), tylko symbol na szczycie stosu może zostać odczytany, tylko symbol na szczycie stosu może zostać usunięty (POP).

Konfiguracja AZS - jest trójką< s, x, w >:
s - stan,
x - łańcuch alfabetu wejściowego,
w - łańcuch alfabetu stosowego.
Łańcuch x jest interpretowany jako wartości wejść pozostałych do przeczytania, w jest zawartością stosu.

AZS jest siódemką uporządkowaną
(Q,
,
,
, q0, Z0, F)

Q - skończony zbiór stanów

- alfabet wejściowy,

- alfabet stosowy,

- stan początkowy,

- symbol stosowy początkowy,

- zbiór stanów końcowych,


- funkcja przejścia.

VII wykład - Rachunek lambda

Rachunek Churcha operuje na obiektach będących matematycznymi funkcjami; Argumenty tych funkcji są także funkcjami; W wyniku działania jednej funkcji na drugą otrzymujemy ponownie funkcję.

Operacja abstrahowania: Oznaczona literą λ; po operacji λ występuje funkcja Churcha (np. x), po niej kropka i nawias kwadratowy, np. λx.[fx]; za każde wystąpienie danej funkcji Churcha (x) w nawiasie należy podstawić wyrażenie za nawiasem (beta-redukcja); zmienna x jest zmienną związaną.

Zmiana nazw zmiennych: nazwa zmiennej związanej nie ma żadnego znaczenia; jej nazwa może być dowolnie zmieniana jeżeli nie występuje kolizja z innymi zmiennymi:

• ၬx.x ွ ၬy.y

• ၬx.y Ⴙ ၬy.y.

Zmiana nazwy zmiennej związanej nazywa się alfa-konwersją(ၬx.[fx]a ွ fa(a->x)).

Za pomocą rachunku lambda można zdefiniować także funkcje, które nie mają standardowych notacji.

Przyjmuje się dwie następujące wartości logiczne Churcha: TRUE = λu.λ v.u; FALSE = λu.λv.v

LISP: przeprowadza obliczenia na wyrażeniach symbolicznych, jest oparty o rachunek lambda. W LISP obecność tylko dwóch struktur danych: atomów i list. Atomy mogą być numeryczne lub symboliczne. Listy mogą być zagnieżdżane i formować drzewa.

Listy można odróżnić od wyrażeń zapisanych w postaci list po znaku cytowania (')

VIII Wykład

Dowolny język wygenerowany przez gramatykę nieograniczoną jest rekurencyjnie przeliczalny. Jest to język akceptowany przez MT.

Automat liniowo ograniczony to MT, której taśma zawiera tylko n komórek, gdzie n jest długością łańcucha wejściowego.

Twierdzenie.

Każda gramatyka bezkontekstowa jest gramatyką kontekstową. Istnieje gramatyka kontekstowa, która nie jest gramatyką bezkontekstową(A=Ab).

Twierdzenie.

Każdy język kontekstowy jest językiem rekursywnym, ale istnieje język rekursywny, który nie jest językiem kontekstowym.

Zawartość: Języki regularne -> języki bezkontekstowe -> języki kontekstowe -> języki rekurencyjnie przeliczalne.

Formalizmy definiujące klasę funkcji częściowo rekurencyjnych:

• Maszyna Turinga,

• Rachunek ၬ (Alonzo Church),

• Maszyna o dostępie swobodnym (RAM).

Maszyna RAM jest modelem komputera, który zawiera

• pamięć w postaci ciągu rejestrów r0, r1,..., ri , ...

• jeden akumulator r0,

• taśmę wejściową do odczytu,

• taśmę wyjściową do zapisu,

• instrukcje, którym nie wolno się modyfikować (program),

• licznik lokalizacji.

Zasady pracy RAM:

• Taśma wejściowa zawiera liczby całkowite,

• Po odczycie symbolu z taśmy głowicy następuje przesuw głowicy w prawo o jeden,

• Na taśmę wyjściową zapisuje się liczby całkowite,

• Gdy symbol wyjściowy zostanie zapisany, nie można go zmienić,

• Program nie jest zapisany w pamięci (nie może więc siebie modyfikować).

Instrukcje dostępne w RAM:

• Instrukcje arytmetyczne,

• Instrukcje we/wy,

• instrukcje adresowania pośredniego (np. przy indeksowaniu do tablic),

• instrukcje rozgałęzienia.

Postaci operandum:

1. =i (liczba całkowita i),

2. i (zawartość rejestru ri, i Ⴓ0),

3. *i (adresowanie pośrednie).

Akceptowanie języków na RAM:

• Napis s jest akceptowany przez program P maszyny RAM, gdy P czyta cały napis s i znacznik końca i pisze 1 w pierwszej klatce taśmy wyjściowej i zatrzymuje się.

• Dla napisów nieakceptowanych maszyna może zwracać inny symbol lub się nie zatrzymywać

• Język jest akceptowany przez program P na maszynie RAM <=> gdy jest rekurencyjnie przeliczalny

• Język jest akceptowany przez zatrzymującą się dla wszystkich danych maszynę RAM <=> gdy jest rekurencyjny.

Maszyną Turninga nazywamy
(Q, , δ,
, q0, B, F),
gdzie

Q - skończony zbiór stanów

- skończony zbiór dopuszczalnych symboli taśmowych,
 - podzbiór niezawierający B - zbiór symboli wejściowych,

q₀ - stan początkowy,
B - symbol pusty,
F - zbiór stanów końcowych,

- funkcja następnego ruchu (L oznacza ruch w lewo, P - w prawo).

Maszyna Turninga: urządzenie obliczające funkcje na liczbach całkowitych.

Język rekurencyjny: podklasa języków rekurencyjnie przeliczalnych, są akceptowane przynajmniej przez jedną MT, która zatrzymuje się na wszystkich wejściach.

Teza Churcha:

• Intuicyjne pojęcie funkcji obliczalnej może być utożsamiane z klasą funkcji częściowo rekurencyjnych.

• Funkcje częściowo rekurencyjne generują MT, maszyna RAM, rachunek λ.

Funkcja f(i1,i2,….,ik) obliczana przez MT jest nazywana funkcją częściowo rekurencyjną.

Jeżeli f(i1,i2,….,ik) jest określone dla wszystkich i1,i2,….,ik ,to f jest nazywana funkcją całkowicie rekurencyjną.

Uniwersalna maszyna Turninga - potrafi udawać dowolną inną maszynę Turninga.

Egrep - służy do przeszukiwania plików tekstowych. ^-początek linii, $ - koniec linii, (^$-pusta linia).

---