Języki formalne _ zaliczenie wykładów_ sciaga.doc

1.Podać definicję języka formalnego.

Język formalny to podzbiór zbioru wszystkich słów nad pewnym alfabetem.

L = <S, Syn, DSem, Sem>

S ‑ 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, S, d, q0, F >

Q ‑ skończony zbiór stanów sterowania.

S ‑ skończony alfabet wejściowy.

d - funkcja przejść: Q ´S ® 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 MN nazywamy system:  MN = < Q, S, d, q0, F >

Q ‑ skończony zbiór stanów sterowania.

S ‑ skończony alfabet wejściowy.

d ‑ funkcja przejść: Q ´S ® 2Q.

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, S, P, S >    N Ç S = Æ

N ‑ skończony niepusty alfabet symboli pomocniczych (nieterminalnych).

S ‑ skończony, niepusty alfabet definiowanego języka (symbole terminalne),

P Í (NÈS)+ ´ (NÈS)*, 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, S, G, d, q0, Z0, F >

Q ‑ skończony zbiór stanów sterowania.

S ‑ skończony alfabet wejściowy.

G ‑ skończony zbiór symboli stosu.

d : Q ´S È {e} ´G ® Q ´ G*‑ funkcja przejść.

q0 Î Q ‑ wyróżniony stan początkowy.

Z0 ÎG ‑ 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, S, G, d, q0, Z0, F >

Q ‑ skończony zbiór stanów sterowania.

S ‑ skończony alfabet wejściowy.

G ‑ skończony zbiór symboli stosu.

d ‑ funkcja przejść: Q ´ S È {e} ´ G ® 2 Q x G*.

q0 Î Q ‑ wyróżniony stan początkowy.

Z0 ÎG ‑ 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, S, P, S > nazywa się bezkontekstową wtw. każda produkcja p Î P przyjmuje postać: A ® u, gdzie A Î N i u Î (N È S)*;

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}, S={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.