Vomlelová 26.5.2020

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
tyneneu
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 28. 1. 2019 18:29
Typ studia: Informatika Bc.

Vomlelová 26.5.2020

Příspěvek od tyneneu »

Písemka:

1.Vyberte všechna pravdivá doplnění věty:

Jazyk Jazyk {0i1n2i| i,n=1,2,... } je:

Vyberte jednu nebo více možností:
a. rozpoznáván jistým konečným automatem
b. rozpoznáván jistým zásobníkovým automatem
c. rozpoznáván jistým deterministickým zásobníkovým automatem koncovým stavem
d. rozpoznáván jistým deterministickým zásobníkovým automatem prázdným zásobníkem

2.Vyberte všechna pravdivá doplnění věty:

Jazyk {0i1n| i,n=0,1,2,... } je:

Vyberte jednu nebo více možností:
a. rozpoznáván jistým konečným automatem
b. rozpoznáván jistým zásobníkovým automatem
c. rozpoznáván jistým deterministickým zásobníkovým automatem koncovým stavem
d. rozpoznáván jistým deterministickým zásobníkovým automatem prázdným zásobníkem Jazyk není bezprefixový, např. slova 0 i 00 patří do jazyka, první je prefixem druhého.

3.Mějme množinu tří řetězců (slov) A={jedna, dve, tri }.

Vyberte všechna pravdivá doplnění věty:

Jazyk A* je:

Vyberte jednu nebo více možností:
a. regulární
b. bezkontextový
c. kontextový
d. rekurzivně spočetný.

4. Vyberte vlastnosti, které po spojení konjunkcí dají dokončení Pumping lemmatu pro bezkontextové jazyky. Vyberte co nejsilnější podobu, tj. požadujte od dělení uvwxy co nejvíce, co lze zaručit.



Začátek Pumping lemmatu:

Mějme bezkontextový jazyk L. Pak existuje konstanta n ∈ N (závislá na L) tak že
každé z∈L ;|z| ≥ n můžeme rozdělit na pět částí, z = uvwxy, že:

Vyberte jednu nebo více možností:
a. |xy| ≤ n
b. |x| = |y|
c. pro každé k ≥ 0, slovo uvkwxky je také v L.
d. pro každé k ≥ 0, slovo xykz je také v L.
e. |vwx| ≤ n
f. |uvw| ≤ n
g. |vx| >0

5.Regulární jazyky můžeme definovat také jako nejmenší třídu jazyků pro konečnou neprázdnou abecedu Σ, která:



obsahuje

prázdný jazyk ∅
pro každé písmeno x ∈ Σ obsahuje

je uzavřená na sjednocení

je uzavřená na zřetězení

je uzavřená na iteraci

jazyk {x}
A,B ∈ RJ(Σ) ⇒ A ∪ B ∈ RJ(Σ)
A,B ∈ RJ(Σ) ⇒ A.B ∈ RJ(Σ)
A ∈ RJ(Σ) ⇒ A∗ ∈ RJ(Σ)

6. Vyberte pravdivá tvrzení:

Vyberte jednu nebo více možností:
a. Pro každý nedeterministický konečný automat existuje deterministický konečný automat přijímající stejný jazyk.
b. Pro každý nedeterministický zásobníkový automat existuje deterministický zásobníkový automat přijímající stejný jazyk koncovým stavem.
c. Pro každý nedeterministický zásobníkový automat existuje deterministický zásobníkový automat přijímající stejný jazyk prázdným zásobníkem.

7.Vyberte pravdivá tvrzení:

Vyberte jednu nebo více možností:
a. Každý jazyk generovaný lineární gramatikou je regulární.
b. Každý jazyk generovaný levou lineární gramatikou je regulární.
c. Každý regulární jazyk lze generovat pravou lineární gramatikou.
d. Každý regulární jazyk lze generovat lineární gramatikou.
e. Každý jazyk generovaný pravou lineární gramatikou je regulární.

8.Na operaci průniku jazyků jsou uzavřené

Vyberte jednu nebo více možností:
a. regulární jazyky
b. bezkontextové jazyky
c. deterministické bezkontextové jazyky

9.Pro oddělení ekvivalentních/rozlišitelných stavů iterujeme algoritmus hledající
rozlišitelné
stavy.

Základ: Pokud p ∈ F (přijímající) a q není v F, pak jsou {p,q}..........
Indukce: Nechť p,q ∈ Q, a ∈ Σ a o dvojici r,s;
......................... víme, že jsou ............... Pak i {p,q} jsou .................

10.Definujeme L jakožto množinu všech w slov nad abecedou {0,1}, která když interpretuji jako Turingův stroj a pustím na samo sebe jako vstup tak vstup nepřijme.



Taková množina: (vyberte pravdivá tvrzení)

Vyberte jednu nebo více možností:
a. Není myslitelná, řetězec nul a jedniček nelze interpretovat jako Turingův stroj.
b. Existuje zásobníkový automat, který ji přijímá.
c. Existuje Turingův stroj, který ji přijímá.
d. Je definovaná slovně, ale neexistuje Turingův stroj, který by přijímal právě taková slova.

11.Napište definici kontextové gramatiky.

12.Najděte (co nejjednodušší) automat (konečný, zásobníkový, lineárně omezený či neomezený Turingův stroj) k následující gramatice:

G=({S,A},{0,1,2},S,P), kde

P={
S→0S1 | A
A→2A1|21
}

Popis buď zapsat nebo přiložit foto náčrtku.

Na ústní jsem dostala otázku na uzavřenost deterministických bezkontextových jazyků (průnik, sjednocení, doplňek) - říct, jestli jsou nebo ne a dokázat nebo uvést protipříklad.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“