JAG

Question 1

Definice: abeceda, slovo nad abecedou, délka slova, zřetězení slov, množiny Σ* a Σ+ , mocniny

Question 2

Vlastnosti operace zřetězení nad Σ* a Σ+

Question 3

Definice: podslovo, prefix, sufix

Question 4

Definice: jazyk nad abecedou

Question 5

Definice: konečný automat, množina stavů, vstupní abeceda, změna stavů, výstup konečného automatu

Question 6

Jaké jsou typy automatů?

Question 7

Definice: Mealyho automat, Mooreův automat, DFA, automat bez vstupů

Question 8

Stavový diagram, rozšířená přechodová funkce + tvrzení o ní, jazyk přijímaný konečným automatem

Question 9

Regulární jazyky, pumping lemma pro regulární jazyky, Nerodova věta

Question 10

Jak dokázat, že daný automat přijímá daný jazyk?

Question 11

Ekvivalentní automaty, dosažitelné stavy + postup jejich nalezení, ekvivalence stavů, redukovaný automat, konstrukce relace, algoritmus redukce

Question 12

Věta o redukovaným automatu a původním automatu (2.1.32)

Question 13

Isomorfní automaty

Question 14

Věta o tom, kdy 2 automaty přijímají stejný jazyk (2.1.34)

Question 15

Nedeterministický automat: definice, stavový diagram NFA, rozšířená přechodová funkce NFA, slovo přijímané NFA, jazyk přijímaný NFA

Question 16

Tvrzení o vztahu DFA a NFA (mezi 2.2.7 a 2.2.8)

Question 17

Podmnožinová konstrukce

Question 18

NFA-ε: definice, jazyk přijímaný, rozšířená přechodová funkce, ε-uzávěr, třída jazyků přijímaných NFA-ε

Question 19

Uzávěrové vlastnosti regulárních výrazů (2. části)

Question 20

Součinová konstrukce

Question 21

Regulární výrazy nad abecedou, Jazyk reprezentující regulární výraz

Question 22

Věta o jazycích reprezentovaných regulárním výrazem (2.5.4)

Question 23

Kleeneho věta (2.5.5)

Question 24

Ekvivalence regulárních výrazů

Question 25

Konstrukce konečného automatu k regulárnímu výrazu

Question 26

Regulární výraz reprezentující jazyk

Question 27

Praktické použití regulárních výrazů

Question 28

Algoritmická řešitelnost úloh pro regulární výrazy

Question 29

Dvousměrné automaty

Question 30

Backus-Naurova forma - číslo

Question 31

Definice: Gramatika, přímé odvození, odvození/derivace, jazyk generovaný gramatikou

Question 32

Chomského hierarchie

Question 33

Nevypouštěcí gramatiky + tvrzení

Question 34

2 tvrzení o vztahu regulárních jazyků a gramatikou č. 3 (3.1.11)

Question 35

CF gramatiky, tvrzení 3.2.1, levá derivace, levé odvození, derivační strom

Question 36

Jednoznačné a víceznačné CF gramatiky, víceznačný jazyk

Question 37

Redukované CF gramatiky, tvrzení 3.2.8, algoritmus redukce CFG

Question 38

Chomského normální tvar

Question 39

Pumping lemma pro CF gramatiky

Question 40

Algoritmus CYK

Question 41

Zásobníkové automaty, situace ZA, jeden krok práce ZA, relace |-A, relace |-A*, stavový diagram ZA

Question 42

Jazyky přijímané ZA: L(A), N(A)

Question 43

Deterministický ZA, jazyky přijímané det. ZA

Question 44

Deterministický jazyk, bezprefixový jazyk

Question 45

Vztah mezi třídami regulárních jazyků, bezprefixových jazyků a deterministckých jazyků

Question 46

Uzávěrová vlastnosti CF jazyků

Question 47

Greibachové normální forma, odstranění levé rekurze