1.Podać definicję języka formalnego. Język formalny to podzbiór zbioru wszystkich słów nad pewnym alfabetem. L = <Σ, Syn, DSem, Sem> Σ - alfabet, skończony niepusty zbiór symboli (znaków). Syn - syntaktyka - zbiór napisów języka, zbudowanych z symboli alfabetu. DSem - dziedzina znaczeń, zbiór bytów semantycznych, przypisywanych języka. Sem - relacja semantyczna (Sem ⊆ Syn × DSem), definiuje związki między napisami języka a elementami dziedziny znaczeń. 2.Scharakteryzować podejście generacyjne i podejście akceptorowe do definiowania składni języka formalnego. W metodach generacyjnych podaje się zbiór reguł generacji poprawnych napisów nad podanym alfabetem (gramatyki kombinatoryczne Chomsky'ego, wyrażenia regularne). W metodach akceptorowych definiuje się nad alfabetem automat/akceptor, który potrafi zbadać przynależność napisu do języka (wszystkie napisy zaakceptowane przez automat definiują język).	3. Hierarchia jęz. wg N. Chomsky'ego: języki klasy "0" nazywamy obliczalnymi, są klasą najszerszą, matematycznie są przykładem zbiorów rekurencyjnie przeliczalnych (częściowo rozstrzygalnych); języki klasy "1" nazywamy monotonicznymi, matematycznie są przykładem zbiorów rekurencyjnych (rozstrzygalnych); języki klasy "2" nazywamy bezkontekstowymi; podklasę stosowaną praktycznie stanowią języki LL i LR (generator YACC); języki klasy "3" nazywamy regularnymi; biorą swą nazwę od jednego z formalizmów ich definiowania zwanego wyrażeniem regularnym	6. DETERMINISTYCZNEGO AUTOMATU SKOŃCZONEGO automatem skończonym deterministycznym MD nazywamy system: MD = < Q, Σ, δ, q0, F > Q - skończony zbiór stanów sterowania. Σ - skończony alfabet wejściowy. δ - funkcja przejść: Q ×Σ → Q. q0 ∈ Q - wyróżniony stan początkowy. F ⊆ Q - zbiór stanów końcowych. przykład (graf funkcji przejść automatu MD1 akceptującego język (a|b)*abb)	7. NIEDETERMINISTYCZNEGO AUTOMATU SKOŃCZONEGO automatem skończonym niedeterministycznym M^N nazywamy system: MN = < Q, Σ, δ, q0, F > Q - skończony zbiór stanów sterowania. Σ - skończony alfabet wejściowy. δ - funkcja przejść: Q ×Σ → 2^Q. q0 ∈ Q - wyróżniony stan początkowy. F ⊆ Q - zbiór stanów końcowych. przykład (graf funkcji przejść automatu MN1 akceptującego język (a|b)*abb)
4. Podać definicję gramatyki kombinatorycznej wg Chomsky'ego i języka generowanego taką gramatyką. przykładem systemu kombinatorycznego jest gramatyka kombinatoryczna (klasa 0), zdefiniowana przez Noama Chomsky'ego: G = < N, Σ, P, S > N ∩ Σ = ∅ N - skończony niepusty alfabet symboli pomocniczych (nieterminalnych). Σ - skończony, niepusty alfabet definiowanego języka (symbole terminalne), P ⊆ (N∪Σ)+ × (N∪Σ)*, zbiór produkcji gramatyki (reguł generacji napisów). S ∈N, wyróżniony symbol pomocniczy, zwany aksjomatem gramatyki. 5.Podać definicję wyrażenia regularnego i zilustrować ją odpowiednim przykładem. Wyrażenia regularne to wzorce, które opisują łańcuchy symboli. Wyrażenia regularne mogą określać zbiór pasujących łańcuchów, mogą również wyszczególniać istotne części łańcucha.	8.Przytoczyć lemat o pompowaniu dla REGULARNYCH. Tw. (lemat o pompowaniu dla języków regularnych) Dla dowolnego języka regularnego L(GR) istnieje liczba naturalna p taka, że jeśli słowo z ∈ L(GR) i |z| ≥ p, to z = uvw oraz: 1. |v| ≥ 1, 2. |uv| ≤ p, 3. każde słowo postaci uviw ∈ L(Gr), i ≥ 0. 12. lemat o pompowaniu dla BEZKONTEKSTOWYCH. Tw. (lemat o pompowaniu dla języków bezkontekstowych) Dla dowolnego języka bezkontekstowego L(GB) istnieje liczba naturalna p taka, że jeśli słowo z ∈ L(GB) i |z| ≥ p, to z = uvwxy oraz: 1. |vx| ≥ 1, 2. |vwx| ≤ p, 3. każde słowo postaci uviwxiy ∈ L(GB), i ≥ 0. 11.Do czego służy notacja BNF? Podać przykład zastosowania. notacja BNF zapisu produkcji gramatyki bezkontekstowej <wyrażenie> ::= <wyrażenie> + <składnik> | <składnik> <składnik> ::= <składnik> * <czynnik> | <czynnik> <czynnik> ::= ( <wyrażenie> ) | a | b Przykład Aby przy pomocy notacji BNF określić liczbę naturalną, można użyć następujących reguł: <zero>::= 0 Wartość: 0 <cyfra niezer>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Przykład wartości: 1,2, 3 <cyfra>::= <zero> | <cyfra niezerowa> Przykład wartości: 0, 1, 2, 3	13. DETERMINISTYCZNEGO automatu ze stosem. automatem deterministycznym ze stosem MDP nazywamy system: MDP = < Q, Σ, Γ, δ, q0, Z0, F > Q - skończony zbiór stanów sterowania. Σ - skończony alfabet wejściowy. Γ - skończony zbiór symboli stosu. δ : Q ×Σ ∪ {ε} ×Γ → Q × Γ*- funkcja przejść. q0 ∈ Q - wyróżniony stan początkowy. Z0 ∈Γ - znacznik dna stosu. F ⊆ Q - zbiór stanów końcowych. 14. NIEDETERMINISTYCZNEGO automatu ze stosem. automatem niedeterministycznym ze stosem MP nazywamy system: MP = < Q, Σ, Γ, δ, q0, Z0, F > Q - skończony zbiór stanów sterowania. Σ - skończony alfabet wejściowy. Γ - skończony zbiór symboli stosu. δ - funkcja przejść: Q × Σ ∪ {ε} × Γ → 2 ^Q x^Γ^*. q0 ∈ Q - wyróżniony stan początkowy. Z0 ∈Γ - znacznik dna stosu. F ⊆ Q - zbiór stanów końcowych.	9.Podać definicję gramatyki bezkontekstowej i zilustrować ją odpowiednim przykładem. gramatyka GB = < N, Σ, P, S > nazywa się bezkontekstową wtw. każda produkcja p ∈ P przyjmuje postać: A → u, gdzie A ∈ N i u ∈ (N ∪ Σ)*; wywód lewostronny(prawostronny) ⇒*L (⇒*R) - ciąg form zdaniowych uzyskiwanych w trakcie wywodu z aksjomatu pewnego zdania x w ten sposób, że w każdym kroku stosuje się produkcję do skrajnie lewego (prawego) symbolu nieterminalnego formy zdaniowej. przykład (gramatyka bezkontekstowa GB1; język prostych wyrażeń arytmetycznych) GB1 = < N={E, T, F}, Σ={a, b, +, *, (, )}, P, E > P = {E → E + T | T, T → T * F | F, F →a | b | (E) } 16.Do jakiej klasy można zaliczyć języki obliczane przez maszyny Turinga? Języki rekurencyjnie przeliczalne (typu 0) to język, dla którego istnieje gramatyka typu 0, której produkcje są postaci α -> β, gdzie α i β są dowolnymi słowami. Języki rekurencyjnie przeliczalne są równoważne maszynom Turinga.
15.MASZYNA TURINGA matematycznie maszyna jest n-tką: T = <Q, Ak, B, I, q0>: Ak -skończony alfabet symboli taśmy, ak jest wyróżniony i oznaczony B („blank”), Q = {q0, q1, …, qn} -skończony zbiór stanów sterowania, q0 - stan początkowy, I - zbiór instrukcji postaci: qi aj an D qm jeśli dla każdego stanu qi w zbiorze instrukcji I maszyny T występuje co najwyżej jedna instrukcja zaczynająca się od qi aj, to maszyna T jest deterministyczna (DTM), dalej	przykład (deterministyczna maszyna Turinga): A3 = {a, b, B}, Q = {q0, q1, q2}, I = {q0aaRq1, q0bbRq1, q0BB0q0, q1aBRq1, q1bBRq1, q1BB0q2} Instrukcję można ilustrować diagramem funkcji przejść:	10.DRZEWO WYWODU. pojęcie drzewa wywodu T : -każdy wierzchołek T jest etykietowany symbolem ze zbioru N ∪ Σ ∪ {ε}, -etykietą korzenia jest aksjomat S, -każdy wierzchołek wewnętrzny jest etykietowany symbolem nieterminalnym, -jeżeli wierzchołek ma etykietę A, a jego wierzchołki potomne, uszeregowane od strony lewej ku prawej etykiety, odpowiednio, X1, X2, … Xn, to w zbiorze P musi istnieć produkcja A → X1X2 …Xn, -jeśli wierzchołek ma etykietę ze zbioru Σ ∪ {ε}, to jest on liściem i jedynym potomkiem -wierzchołka bezpośrednio nadrzędnego; przykład (przedstawienie wywodu napisu (a+b)*a w postaci drzewa wywodu) dalej -

---