JAG
Z OI wiki
(→7.1.2011 10:00: zTeXovány matematické výrazy a doplněno/upraveno) |
(→Zkoušky: doplněna zkouška ze 14.11.2011) |
||
Řádka 24: | Řádka 24: | ||
== Zkoušky == | == Zkoušky == | ||
+ | |||
+ | === 14.1.2011 10:00 === | ||
+ | |||
+ | '''1)''' Je dán jazyk <math>L_1</math>: <math> \mathbf{r} = (a^*(a + b)b + b(a + b))^* </math> | ||
+ | a jazyk <math>L_2</math>: | ||
+ | |||
+ | <math>\begin{tabular}{|r|r|r|} | ||
+ | \hline | ||
+ | \bf & \bf a & \bf b \\ | ||
+ | \hline | ||
+ | \bf in 1 & \bf 2 & \bf 4 \\ | ||
+ | \hline | ||
+ | \bf 2 & \bf 3 & \bf 4 \\ | ||
+ | \hline | ||
+ | \bf out 3 & \bf 4 & \bf 3 \\ | ||
+ | \hline | ||
+ | \bf 4 & \bf 4 & \bf 4 \\ | ||
+ | \hline | ||
+ | \end{tabular}</math> | ||
+ | ''pokud někdo ví jak na šipky in/out, prosím doplňte'' | ||
+ | |||
+ | a) [10b] Sestrojte DFA <math>M_1</math> pro<math>L_1</math>, zdůvodněte, proč jazyk přijímá. | ||
+ | b) [ 4b] Napište regulární výraz pro jazyk <math>L_2</math>. | ||
+ | c) [ 8b] Rozhodněte, zda platí <math>L_1 \subseteq L_2</math>, zdůvodněte nebo uveďte protipříklad. | ||
+ | d) [ 8b] Rozhodněte, zda platí <math>L_2 \subseteq L_1</math>, zdůvodněte nebo uveďte protipříklad. | ||
+ | |||
+ | '''2)''' Je dána gramatika <math>G = (N, \Sigma, S, P)</math>, kde <math>N = {S, A, B, C} , \Sigma = {0, 1}</math> | ||
+ | a pravidly P: S -> AB, A -> AC|0, B -> BC|<math>\varepsilon</math>, C -> AS|1 | ||
+ | |||
+ | a) [ 8b] Převeďte gramatiku <math>G</math> do Chomského normálního tvaru a napište co to je. | ||
+ | b) [ 6b] Generuje gramatika <math>G</math> slovo '00011', zdůvodněte. | ||
+ | c) [ 6b] Ukažte, že <math>G</math> je víceznačná a popište, co to znamená. | ||
+ | |||
+ | '''3)''' Je dán jazyk <math> L = \{a^n b^{n+2} | n > 0\} </math> | ||
+ | |||
+ | a) [12b] Sestrojte zásobníkový automat, který přijímá koncovým stavem. Pečlivě popište. | ||
+ | b) [ 5b] Ukažte výpočet zásobníkového automatu z a) na slově <math>u = a^2b^4</math>. | ||
+ | c) [ 7b] k zásobníkovému automatu z a) zkonstruujte zásobníkový automat, | ||
+ | který přijímá jazyk <math>L</math> prázdným zásobníkem. | ||
+ | |||
+ | '''4)''' Je dán jazyk <math> L = \{1^{n+1} 2 0^m 2 1^{n+1} | m < n\} </math> | ||
+ | |||
+ | a) [12b] Rozhodněte, zda je jazyk <math>L</math> bezkontextový. Definujte, co to je bezkontextový jazyk. | ||
+ | b) [12b] Rozhodněte, zda je jazyk <math>L</math> regulární. Definujte, co to je regulární jazyk. | ||
+ | |||
+ | |||
=== 7.1.2011 10:00 === | === 7.1.2011 10:00 === |
Verze z 14. 1. 2011, 13:48
|
|
Info o předmětu
- Přednášející: prof. RNDr. Marie Demlová, CSc.
- Cvičící: M. Demlová, J. Demel
Pravidla předmětu
Studijní materiály
Velice pěkná PDF na JAG z matfyzu. http://ktiml.mff.cuni.cz/~bartak/automaty/prednaska.html
Zkoušky
14.1.2011 10:00
1) Je dán jazyk : a jazyk : pokud někdo ví jak na šipky in/out, prosím doplňte a) [10b] Sestrojte DFA pro, zdůvodněte, proč jazyk přijímá. b) [ 4b] Napište regulární výraz pro jazyk . c) [ 8b] Rozhodněte, zda platí , zdůvodněte nebo uveďte protipříklad. d) [ 8b] Rozhodněte, zda platí , zdůvodněte nebo uveďte protipříklad.
2) Je dána gramatika , kde a pravidly P: S -> AB, A -> AC|0, B -> BC|, C -> AS|1 a) [ 8b] Převeďte gramatiku do Chomského normálního tvaru a napište co to je. b) [ 6b] Generuje gramatika slovo '00011', zdůvodněte. c) [ 6b] Ukažte, že je víceznačná a popište, co to znamená.
3) Je dán jazyk a) [12b] Sestrojte zásobníkový automat, který přijímá koncovým stavem. Pečlivě popište. b) [ 5b] Ukažte výpočet zásobníkového automatu z a) na slově . c) [ 7b] k zásobníkovému automatu z a) zkonstruujte zásobníkový automat, který přijímá jazyk prázdným zásobníkem.
4) Je dán jazyk a) [12b] Rozhodněte, zda je jazyk bezkontextový. Definujte, co to je bezkontextový jazyk. b) [12b] Rozhodněte, zda je jazyk regulární. Definujte, co to je regulární jazyk.
7.1.2011 10:00
1. [30b] Dva regulárne výrazy:
a) [10b] Zostrojte DFA pre reg. výraz (jazyk ) a DFA pre reg. výraz (jazyk ).
b) [10b] Zostrojte DFA pre rozdiel jazykov
c) [5b] Automat redukujte
d) [5b] Napíšte regulárny výraz odpovedajúci automatu
2. [25b] Daný je jazyk
a) [13b] Zostrojte jeho CFG gramatiku, zdôvodnite, že daná gramatika popisuje jazyk .
b) [12b] Preveďte gramatiku na Chomského normální tvar (Definujte, čo je Choms. norm. tvar)
3. [21b] Je dána gramatika:
S -> aSA | bB A -> aAb | b B -> aA
a) [10b] Zostrojte zásobníkový automat
b) [6b] Popište výpočet zásobníkového automatu z bodu a) přijímající slovo abababb.
c) [5b] Ukažte, že slovo aabbba není přijímáno zásobníkovým automatem.
4. [24b] Daný je jazyk
a) [12b] Dokažte, zda jazyk je bezkontextový. (Definujte bezkontextový jazyk.)
a) [12b] Dokažte, zda jazyk je regulární. (Definujte regulární jazyk.)