JAG Flashcards

Jazyky, Automaty, Gramatiky https://docs.google.com/document/d/1QW6bqV5cCkpwsj9eBODKTO6u-2nRSqRklsXkx5MxQ9k/edit#

1
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Definice: podslovo, prefix, sufix

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Definice: jazyk nad abecedou

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Jaké jsou typy automatů?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Isomorfní automaty

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Podmnožinová konstrukce

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

20
Q

Součinová konstrukce

21
Q

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

22
Q

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

23
Q

Kleeneho věta (2.5.5)

24
Q

Ekvivalence regulárních výrazů

25
Q

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

26
Q

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

27
Q

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

28
Q

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

29
Q

Dvousměrné automaty

30
Q

Backus-Naurova forma - číslo

31
Q

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

32
Q

Chomského hierarchie

33
Q

Nevypouštěcí gramatiky + tvrzení

34
Q

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

35
Q

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

36
Q

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

37
Q

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

38
Q

Chomského normální tvar

39
Q

Pumping lemma pro CF gramatiky

40
Q

Algoritmus CYK

41
Q

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

42
Q

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

43
Q

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

44
Q

Deterministický jazyk, bezprefixový jazyk

45
Q

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

46
Q

Uzávěrová vlastnosti CF jazyků

47
Q

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