1. Definicja automatu skończonego

Abstrakcyjny, matematyczny, iteracyjny model zachowania systemu dynamicznego oparty o tablicę dyskretnych przejść między jego kolejnymi stanami

DAS - 1 symbol = przejście do 1 stanu; NAS - 1 symbol = przejście do >= 1 stanu

2. Definicja języka akceptowanego przez automat skończony

Mówimy że łańcuch x jest akceptowany przez automat skończony jeżeli po wykonaniu ∂ (q0, x) = p i p należy do F (zbioru stanów końcowych). Zbiór łańcuchów akceptowanych przez automat to język akceptowany.

3. Wyjaśnij oznaczenia: L₂, (r+s)*

L - język akceptowalny; L₂ - jest przykładowym językiem, np. L₂={011, 11}; r,s - wyrażenia regularne reprezentujące języki R i S; (r+s) - suma tych zbiorów; * - domknięcie Kleene'go

3') Definicja i własności wyraŜeń regularnych

WyraŜenia regularne nad Σ definiujemy rekursywnie:

∅, ε są WR, dla kaŜdego a∈Σ, {a} jest WR ( wszystkie a∈Σ są WR )

JeŜeli a i b są WR, to są nimi rownieŜ:

a* (domknięcie Kleene'ego)

ab (konkatenacja)

a+b (suma)

Własności:

• e + e = e

• e1 + e2 = e2 + e1 - suma jest przemienna

• εe = eε = e - łańcuch pusty jest elementem neutralnym konkatenacji

• (e1 + e2) + e3 = e1 + (e2 + e3) - suma jest łączna

• (e1e2)e3 = e1(e2e3) - konkatenacja rownieŜ jest łączna

• (e1 + e2)X = e1X + e2X - konkatenacja jest rozdzielna względem sumy

• X(e1 + e2) = Xe1 + Xe2

• e * e = ee *

• (e * ) * = e * - domknięcie Kleene'ego jest idempotentne

• e * e * = e *

(a) (grupowanie)

4. Podaj twierdzenie dotyczące wyrażeń regularnych

Jeżeli r będzie WR, to istnieje NAS z Epsilon przejściami, który akceptuje L(r). LUB Jeżeli L jest akceptowane przez DAS to L jest reprezentowany przez WR.

5. Definicja automatu Moore'a.

Rodzaj DAS, reprezentowany przez

uporządkowaną szóstkę (Z,Q,Y, Φ, Ψ, q₀) , gdzie: Z - zbiór sygnałów wejściowych; Q - zbiór stanów wewnętrznych; Y - zbiór sygnałów wyjściowych; Φ - funkcja przejść; Ψ - funkcja wyjść; q₀ - stan wejściowy

6. Wyjaśnij związek między automatem ze stosem i językiem bezkontekstowym

Jeżeli L jest JBK to istnieje AZS taki że: L=N(M)

Domyślnie przyjmuje się, że ten automat jest NAS. Są one równoważne pod względem siły wyrazu gramatykom bezkontekstowym, rozpoznając języki bezkontekstowe.

7. Definicja i opis maszyny Turinga.

Stworzony przez Alana Turinga abstrakcyjny model komputera służący do w wykonywania algorytmów. Każdy algorytm wyrażalny na maszynie Turinga można wyrazić w rachunku lambda i odwrotnie.
MT = < Q, Σ, δ, Γ, q₀, B, F >: Q - skończony zbiór stanów; q₀ - stan początkowy, q₀ należy do Q; F - zbiór stanów końcowych; Γ - skończony zbiór dopuszczalnych symboli; B - symbol pusty, B należy do Γ; Σ - zbiór symboli wejściowych - podzbiór zbioru Γ, do którego nie należy B; δ - funkcja opisana następująco:

co oznacza że jest to funkcja pobierająca aktualny stan maszyny oraz symbol wejściowy a dającą w wyniku symbol jaki ma się pojawić na taśmie, kolejny stan maszyny oraz przesunięcie głowicy maszyny (lewo, prawo lub bez przesunięcia).

8. Własności języków rekurencyjnie przeliczalnych.

Języki rekurencyjnie przeliczalne są zamknięte ze względu na następujące operacje: Domknięcie Kleene'ego L ^* z L ; Konkatenację L o P języków L oraz P; Sumę L u P; Przecięcie L /\ P

Z wykładów: Dopełn. JR=JR; JRuJR=JR; JRPuJRP=JRP

9. Twierdzenie o hierarchii czasowej

Dla dowolnego całkowicie rekurencyjnego ograniczenia czasowego (pamięciowego) f(n) istnieje język rekurencyjny L nie należący do DCZAS(f(n)) lub DPAM(f(n)).

10. Definicja niedeterministycznego automatu skończonego.

Maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa. Po przeczytaniu każdego symbolu zmienia ona swój stan na stan będący elementem zbioru, który jest wartością funkcji przejścia. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), mówimy że automat akceptuje czytane słowo.

Formalnie NAS można przedstawić jako piątkę uporządkowaną (S, ∑, T, s, A), gdzie: S jest skończonym zbiorem stanów; ∑ jest skończonym zbiorem nazywanym alfabetem; T: S × ∑ → P(S) jest funkcją przejścia; s jest stanem początkowym; A jest zbiorem stanów akceptujących (końcowych); P(S) jest zbiorem potęgowym zbioru stanów S.

11. Definicja języka regularnego

Język formalny taki, że istnieje automat o skończonej liczbie stanów potrafiący zdecydować, czy dane słowo należy do języka. Wszystkie języki regularne są bezkontekstowe.

12. Wyjaśnij oznaczenia: L1, L2, L+

L+ - domknięcie dodatnie zbioru L (suma zbiorów od i do nieskończoności)

13. Definicja automatu Mealy'ego.

Definicja intuicyjna:

Automat Mealy'ego przedstawia się jako graf skierowany z wyróżnionym wierzchołkiem zwanym stanem początkowym. Podając sygnały na wejście automatu powodujemy zmianę bieżącego stanu i zwrócenie wartości przypisanej do podanego sygnału wejściowego

Opis jak u Moore'a

14. Jak skonstruować DAS o minimalnej liczbie stanów.

Do każdego DAS istnieje jednoznaczny automat minimalny, który akceptuje ten sam język.

Algorytm minimalizacji

1. Usuń z automatu wszystkie stany, które nie są osiągalne ze stanu początkowego.

2. Utwórz tabelę par stanów automatu {Xi, Xj} , gdzie Xi!=Xj.

2.1. Zaznacz wszystkie pary stanów, gdzie XiєF, a Xj nie .

2.2. Dla każdej nie zaznaczonej jeszcze pary stanów oraz dla każdego elementu aєA sprawdź, czy

para {d(Xi,a), d(Xj,a)} jest zaznaczona. Jeśli tak, zaznacz również {Xi, Xj}.

2.3. Powtarzaj krok 2.2. tak długo, dopóki żadna zmiana w tabeli nie będzie już możliwa.

2.4. Każda para, która pozostała niezaznaczona, zostaje stopiona do jednego stanu.

15. Co to jest gramatyka bezkontekstowa?

Gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci: a->T

gdzie A jest dowolnym symbolem nieterminalnym i jego znaczenie nie zależy od kontekstu, w jakim występuje, a T to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.. Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.

Gramatyka bezkontekstowa (GBK) to czwórka uporządkowana: G=(V, T, P, S) gdzie:

V i T - są odpowiednio skończonymi zbiorami zmiennych i symboli końcowych. Zakładam że V i T są rozłączne. P - skończony zbiór produkcji, kaŜda produkcja ma postać A -> α, a α jest łańcuchem

symboli z (V u T)* {u - suma zbiorów}. S jest specjalną zmienną zwaną symbolem początkowym.

16. Wyjaśnij termin “język rekurencyjnie przeliczalny”

Istnieje kilka równoważnych definicji języka rekurencyjnie przeliczalnego:

1. Rekurencyjnie przeliczalny podzbiór zbioru wszystkich słów nad danym alfabetem.

2. Język formalny, dla którego istnieje maszyna Turinga lub inna funkcja obliczalna, która jest w stanie ponumerować wszystkie słowa języka.

3. Język formalny L, dla którego problem czy słowo x należące do L jest nierozstrzygalny^[1].

17. Definicja złożoności czasowej

Liczba operacji podstawowych (np. prostych operacji arytmetycznych, podstawienie, porównanie) zależnych od danych wejściowych „n”

18. Problemy klasy P i NP.

Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla ktorego rozwiązanie moŜna

znaleźć w czasie wielomianowym.

Problem NP (niedeterministycznie wielomianowy, ang. nondeterministic polynomial) to problem decyzyjny, dla ktorego rozwiązanie

moŜna zweryfikować w czasie wielomianowym.

Jednym z najwaŜniejszych problemow informatyki jest pytanie czy P=NP. Wiadomo, Ŝe P⊆NP, nie wiadomo natomiast, czy istnieje

problem NP, ktory nie jest w klasie P.

19. RoŜnica miedzy MT a automatem skończonym

RoŜnica pomiędzy MT a dwukierunkowym DASem polega na tym, Ŝe MT moŜe zmienić stań, z ktorego wychodzi.

20. Związek między DPAM(P(n)) i NPAM(P(n)) oraz DCZAS(P(n)) i NCZAS(P(n)).

DPAM(P(n)) - rodzina językow o deterministycznej złoŜoności pamięciowej P(n), NPAM(P(n)) - o niedeterministycznej.

Problem klasy DPAM(P(n)) moŜe być rozwiązany na DMT z uŜyciem O(P(n)) pamięci, NPAM na NMT z uŜyciem O(P(n)) pamięci.

NPAM(P(n))⊆DPAM(P2(n))

---