Definicja automatu skończonego (DAS) - piątka uporządkowana M=(Q, Σ, δ, q₀, F), gdzie Q jest skończonym zbiorem stanów, Σ jest skończonym alfabetem wejściowym, δ - funkcja przejścia jest odwzorowaniem Q×Σ → Q, q₀ należące do Q jest stanem początkowym, F ⊆ Q jest zbiorem stanów końcowych „stanowiących sukces”.

Definicja niedeterministycznego automatu skończonego (NAS) – to piątka uporządkowana (Q,∑,δ,q₀,F) piątka uporządkowana M=(Q, Σ, δ, q₀, F), gdzie Q jest skończonym zbiorem stanów, Σ jest skończonym alfabetem wejściowym, q₀ należące do Q jest stanem początkowym, F ⊆ Q jest zbiorem stanów końcowych „stanowiących sukces”, δ - funkcja przejścia jest odwzorowaniem Q×∑ → 2_­^Q

Definicja automatu Moore’a - to szóstka uporządkowana (Q,Σ,Δ,δ,λ,q₀), gdzie Q jest skończonym zbiorem stanów, Σ jest skończonym alfabetem wejściowym, δ - funkcja przejścia jest odwzorowaniem Q×Σ → Q, q₀ należące do Q jest stanem początkowym, Δ jest alfabetem wyjściowym, λ - funkcja wyjścia jest odwzorowaniem Q → Δ

Definicja automatu Mealy’ego – to szóstka uporządkowana M=(Q,∑,∆,δ,λ,q₀) gdzie Q jest skończonym zbiorem stanów, Σ jest skończonym alfabetem wejściowym, δ - funkcja przejścia jest odwzorowaniem Q×Σ → Q, q₀ jest stanem początkowym, Δ jest alfabetem wyjściowym, λ - funkcja wyjścia jest odwzorowaniem Q×∑→∆ (zależy od drogi którą się idzie i gdzie się znajduje).

Definicja i opis maszyny Turinga – M=(Q, Σ,δ,Γ,q₀,B,F) gdzie Q – skończony zbiór stanów, Γ – skończony zbiór dopuszczalnych symboli taśmowych, B – symbol pusty nienależący do Γ, ∑ - podzbiór Γ niezawierający B zwany zbiorem symboli wejściowych, δ – funkcja przejścia odwzorowuje Q× Γ → Q× Γ×{L,P}, q_0­ – należące do Q jest stanem początkowym, a F ⊆ Q jest zbiorem stanów końcowych „stanowiących sukces”.

Definicja automatu ze stosem – to siódemka uporządkowana M=(Q, Σ,δ,Γ,q₀,z­­₀,F) gdzie Q – skończony zbiór stanów, ∑ - skończony alfabet wejściowy, Γ – skończony alfabet stosowy, z­­₀ należący do F – symbol początkowy stosu , δ - funkcja przejścia odwzorowuje Qx(Σu{Ɛ})xΓ→2^2xF* (Ɛ-symbol wyjścia, Γ-symbol na stosie), q_0­ – należące do Q jest stanem początkowym, a F ⊆ Q jest zbiorem stanów końcowych „stanowiących sukces”.

Co oznacza stwierdzenie, że dwa p i q automatu skończonego są odróżnialne? - dwa stany p i q są odróżnialne, gdy:.

Podaj twierdzenie dotyczące wyrażeń regularnych – 1) niech r będzie WR, wtedy istnieje NAS z Ɛ-przejściami akceptujący L(r).

2) Jeżeli L jest akceptowany przez DAS, to L jest reprezentowany przez WR.

Definicja WR – ciąg znaków pozwalające opisać WR 1) zb. pusty jest WR 2) Ɛ jest WR (słowo puste) 3) każdy znak alfabetu a należy do ∑ jest WR 4) jeśli r i s są WR reprezentującymi języki R i S, to r+s, rs i r^* są WR reprezentującymi RuS, RnS, R^*

Twierdzenie o hierarchii czasowej – jeżeli C_2­(n) jest funkcją w pełni konstruowalną czasowo oraz $\operatorname{}\frac{{C_{1}(n)\log{C_{1}(n)}}_{\ }}{C_{2}(n)} = 0$ to istnieje język L ∈ DCZAS(C­₂(n)) i L (nie)∈ DCZAS (C­₁(n)).

Twierdzenie o hierarchii pamięciowej – jeśli f(n) jest funkcją konstruowalna pamięciowo oraz g(n) ∈ o(f(n)) (czyli rośnie asymptotycznie wolniej) to SPACE (g(n)) c SPACE (f(n))

Jak skonstruować DAS o minimalnej liczbie stanów – DAS skonstruowany ze wszystkich par stanów odróżnialnych (z usuniętymi stanami nieosiągalnymi) jest automatem o minimalnej liczbie stanów dla swego języka L.

Co to jest gramatyka bezkontekstowa (GBK) – G=(V,T,P,S) gdzie V – skończony zbiór zmiennych końcowych, T – skoń. zb. symboli końcowych, P – skoń. zb. produkcji gdzie każda produkcja ma postać A→ α, gdzie A jest zmienną, a α jest łańcuchem symboli z (VuT)*, S – symbol początkowy (zmienna specjalna); VnT=ø

Definicja języka akceptowanego przez automat skończony - łańcuch x jest akceptowany przez automat skończony jeśli L(M)={x: δ(q₀,x) należy do F}.

Wyjaśnij oznaczenia L^­_1­, L₂, L⁺, L^x, (r+s)^* - L^­_1­, L₂ - zbiór łańcuchów; L⁺ - domknięcie dodatnie zbioru; L^x - suma teoriomnogościowa; (r+s)* - domknięcie sumy języków r i s, ponieważ r i s są wyrażeniami regularnymi, reprezentującymi odpowiednio języki R i S, (r+s) reprezentuje RuS, a R* oznacza domknięcie.

Wyjaśnij związek między automatem ze stosem i językiem bezkontekstowym - jeśli L jest językiem bezkontekstowym, to istnieje automat ze stosem M taki że L=N(M), gdzie N(M) jest językiem akceptowanym przez M.

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

1) Dopełnienie języka rekurencyjnego jest językiem rekurencyjnym

2) Suma teoriomnogościowa dwóch języków rekurencyjnych jest językiem rekurencyjnym.

3) Suma teoriomnogościowa dwóch języków rekurencyjnie przeliczalnych jest językiem rekurencyjnie przeliczalnym

Jeśli zarówno L, jak i jego dopełnienie L’ są rekurencyjnie przeliczalne, to L (a więc i L’) jest rekurencyjny.

Definicja języka regularnego (JR) – jest zbiorem regularnym jeśli jest akceptowany przez 2DAS (jakiś dwukierunkowy automat skończony).

Wyjaśnij termin „język rekurencyjnie przeliczalny” – tak nazywamy język akceptowany przez maszynę Turinga.

Definicja złożoności czasowej – niech M oznacza Maszynę Turinga z k taśmami dwustronnie nieskończonymi. Wejście znajduje się na jednej tych taśm. Jeśli dla każdego słowa wejściowego o dł. n maszyna M wykona C(n) ruchów, to mówimy że M jest Maszyną Tur. z ograniczeniem czasowym C(n) lub o złożoności czasowej C(n).

DAS a MT – MT może zmienić stan z którego wychodzi.