JAG
Z OI wiki
|
|
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
Řešené příklady stylem prezentací, velmi šikovné: http://www.cs.vsb.cz/kot/animace.php
Velice pěkná PDF na JAG z matfyzu. http://ktiml.mff.cuni.cz/~bartak/automaty/prednaska.html
Zkoušky
28.1.2011 10:00
Pomoc s riešením príkladu:
1.c) Sestrojte deterministický konečný automat přijímajíci průnik jazyků.
Vie niekto, ako to vyriešiť? Prehľadal som už všetky možné zdroje a nemôžem nájsť žiaden algoritmus alebo návod ako daný prienik získať. Vďaka --Noskoja1 31. 1. 2011, 20:01 (UTC)
-> zkus se podívat sem, strana 52 - na průnik používá stromvý algoritmus (str. 49). Snad to pomůže ;) --Hanx 31. 1. 2011, 22:26 (UTC)
14.1.2011 10:00
1) [30b] Je dán jazyk : a jazyk : 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) [20b] 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) [24b] 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) [24b] 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.)