JAG
Z OI wiki
(Rozdíly mezi verzemi)
(→Zkoušky: doplněna zkouška ze 14.11.2011) |
m (→7.1.2011 10:00: pouze sjednocení vzhledu zkousek) |
||
Řádka 73: | Řádka 73: | ||
=== 7.1.2011 10:00 === | === 7.1.2011 10:00 === | ||
- | 1 | + | '''1)''' [30b] Dva regulárne výrazy: |
+ | |||
+ | <math> \mathbf{r_1} = b^*aa^*b(a + b)^* </math> <math> \mathbf{r_2} = (a + b)^*b </math> | ||
+ | |||
+ | a) [10b] Zostrojte DFA <math>M_1</math> pre reg. výraz <math>\mathbf{r_1}</math> (jazyk <math>L_1</math>) a DFA <math>M_2</math> pre reg. výraz <math>\mathbf{r_2}</math> (jazyk <math>L_2</math>). | ||
+ | b) [10b] Zostrojte DFA <math>M</math> pre rozdiel jazykov <math>L = L_1 - L_2</math> | ||
+ | c) [ 5b] Automat <math>M</math> redukujte | ||
+ | d) [ 5b] Napíšte regulárny výraz odpovedajúci automatu <math>M</math> | ||
- | <math> \ | + | '''2)''' [25b] Daný je jazyk <math> L = \{0^n 1^m 2^{n+m} | n \ge 0, m > 0\} </math> |
+ | |||
+ | a) [13b] Zostrojte jeho CFG gramatiku, zdôvodnite, že daná gramatika popisuje jazyk <math>L</math>. | ||
+ | b) [12b] Preveďte gramatiku na Chomského normální tvar (Definujte, čo je Choms. norm. tvar) | ||
- | + | '''3)''' [21b] Je dána gramatika pravidly: | |
+ | |||
+ | '''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 <math> L = \{1^{2k} 2^{3l+1} | k,l \ge 0\} </math> | |
- | + | ||
- | + | a) [12b] Dokažte, zda jazyk <math>L^*</math> je bezkontextový. (Definujte bezkontextový jazyk.) | |
- | + | b) [12b] Dokažte, zda jazyk <math>L^*</math> je regulární. (Definujte regulární jazyk.) | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | a) [12b] Dokažte, zda jazyk <math>L^*</math> je bezkontextový. (Definujte bezkontextový jazyk.) | + | |
- | + | ||
- | + |
Verze z 14. 1. 2011, 16:10
|
|
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 pravidly: 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.) b) [12b] Dokažte, zda jazyk je regulární. (Definujte regulární jazyk.)