1 Generativní gramatika a její použití pro definici formálních jazyků, regulární jazyky, bezkontextové jazyky, Chomského hierarchie formálních jazyků.

Question 1

Abeceda

Answer 1

= neprázdná konečná množina symbolů

Question 2

Slovo

Answer 2

= řetězec prvků abecedy konečné délky (může být i prázdný)

Question 3

Jazyk

Answer 3

= jakákoliv podmnožina slov nad danou abecedou

Question 4

Gramatika

Answer 4

= systém, který pomocí pravidel popisuje, jak vytvářet z abecedy slova

Question 5

Generativní gramatika

Answer 5

= gramatika, která poskytuje algoritmický postup, jak vytvořit (generovat) všechna platná slova (řetězce) v jazyce

• Snaha o formální přesnost jako v přírodních vědách
• Oproti gramatice v přirozených jazycích je generativní gramatika explicitním popisem, jak vytvořit veškerá platná slova v daném jazyce
• Používá se pro popis formálních jazyků pomocí pravidel a symbolů
• Může být popsána různými formálními modely, ty jsou hierarchicky uspořádány v tzv. Chomského hierarchii, která ukazuje, jak jsou silné a jaký typ jazyků mohou generovat

Gramatika je tedy čtveřice (N, T, P, S), kde:
- N – množina neterminálních symbolů (proměnné)
- T – množina terminálních symbolů (hodnoty)
- P – množina (přepisovacích) pravidel
- S – startovací symbol (S ∈ N)

Question 6

Formální jazyk

Answer 6

= množina konečných řetězců (slov konečné délky), které příslušná gramatika generuje

Jeden jazyk může mít více příslušných gramatik

Question 7

Regulární jazyky

Answer 7

3, Regulární gramatika, Regulární jazyky, Konečným automatem

Question 8

Bezkontextové jazyky

Answer 8

2, Bezkontextová gramatika, Bezkontextové jazyky, Zásobníkovým automatem

Question 9

Kontextové jazyky

Answer 9

1, Kontextová gramatika, Kontextové jazyky, Lineárně ohraničeným Turing. strojem

Question 10

Obecné jazyky

Answer 10

0, Obecná gramatika, Obecné jazyky, Turingovým strojem

Question 11

Chomského hierarchie

Answer 11

= Klasifikace jazyků / gramatik

Vymezuje čtyři typy gramatik podle tvaru pravidel

Platí, že jazyky generované gramatikami typu 3 jsou podmnožinou jazyků generovaných gramatikami typu 2 atd.

TYP, GRAMATIKA, GENERUJE, JE ROZPOZNATELNÝ:
0, Obecná gramatika, Obecné jazyky, Turingovým strojem
1, Kontextová gramatika, Kontextové jazyky, Lineárně ohraničeným Turing. strojem
2, Bezkontextová gramatika, Bezkontextové jazyky, Zásobníkovým automatem
3, Regulární gramatika, Regulární jazyky, Konečným automatem