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
přepis zadání --Hanx 2. 2. 2011, 18:15 (UTC)
1) [30b] Je dán jazyk : a jazyk : a) [10b] Sestrojte konečný DFA pro , zdůvodněte fakt, že jazyk přijímá. b) [ 5b] Napište regulární výraz odpovídající jazyku . c) [10b] Sestrojte konečný DFA přijímající průnik jazyků . d) [ 5b] Výsledný automat redukujte. -------------------------------------------------------------------------------------------------------------------------------------------- Ad c) 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) -> mas dve DFA pro dva jazyky, sloucis jejich vstupni stavy, na zaklade toho vyrobis novy DFA, pokud chces prunik, tak vystupni stavy jsou ty, kde se slouci vystupni stav 1. a 2. DFA (pokud sjednoceni, tak staci aby to byl bud vystupni 1. nebo 2. DFA, pokud rozdil jazyku, tak jsou vystupni stavy jen ty, kde se slucuje vystupni stav prvniho, se stavem, ktery neni vystupni v druhem) --Adamema4 1. 2. 2011, 10:38 (UTC)
2) [24b] Je dána bezkontextová gramatika , kde a pravidly P: S -> BAC|AC A -> BA| B -> BB|b C -> BC|a a) [10b] Ke gramatice najděte gramatiku v Chomském normálním tvaru, která keneruje stejný jazyk jako . b) [ 8b] Najděte levou derivaci slova 'bbbba' v každé z gramatik a . c) [ 6b] Najděte slovo délky alespoň 5, které není generováno gramatikou , zdůvodněte. -------------------------------------------------------------------------------------------------------------------------------------------- \\Jak presne urcim zda je jazyk bezkontextovy ci nikoli to same pro regularni jazyk...pripadne nejake materialy predem diky
3) [22b] Jsou dány dva jazyky a nad abecedou , a a) [ 8b] Sestrojte bezkontextovou gramatiku , která generuje jazyk . b) [ 8b] Sestrojte bezkontextovou gramatiku , která generuje jazyk c) [ 6b] Sestrojte bezkontextovou gramatiku , která generuje jazyk
4) [24b] Je dán jazyk nad abecedou . 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.
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.)