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

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”

---