Teorie Jazyků

Question 1

Co je abeceda?

Answer 1

Konečná neprázdná množina symbolů. Prvky abecedy se nazývají písmena.

Question 2

Co je řetězec?

Answer 2

Libovolná „konečná posloupnost“ (tj. uspořádaná n-tice) písmen abecedy.

Question 3

Uzávěr abecedy ∑ a jeho značení.

Answer 3

Množina všech neprázdných řetězců vytvořených z písmen abecedy ∑.
Značí se ∑+.

Question 4

Iterace abecedy ∑ a její značení.

Answer 4

Množina všech řetězců vytvořených z písmen abecedy ∑.
Značí se ∑*.

Question 5

Rozdíl mezi iterací abecedy a uzávěrem?

Answer 5

∑* = ∑+ ∪ {e}

Question 6

Jaké jsou operace nad řetězci?

Answer 6

• Zřetězení řetězců: ∑* × ∑* → ∑*
• Mocnina řetězce: ∑* × N0 → ∑*
• Reverze (obrácení) řetězce: ∑* → ∑*
• Délka řetězce: ∑* → N0

Question 7

Co je jazyk L nad abecedou ∑?

Answer 7

Libovolná množina řetězců nad abecedou ∑ , tedy L ⊆ ∑∗.

Question 8

Jaké jsou operace nad jazyky
L1 a L2 jsou jazyky nad abecedou ∑ , tedy L1 ⊆ ∑∗ , L2 ⊆ ∑∗?

Answer 8

• Sjednocení jazyků: L = L1 ∪ L2
  L = {𝑤| 𝑤 ∈ ∑∗ ∧ 𝑤 ∈ L1 ∨ 𝑤 ∈ L2 }
• Průnik jazyků: L = L1 ∩ L2
  L = {𝑤| 𝑤 ∈ ∑∗ ∧ 𝑤 ∈ L1 ∧ 𝑤 ∈ L2 }
• Doplněk jazyka: L = 𝐿1
  L = {𝑤| 𝑤 ∈ ∑∗ ∧ 𝑤 ∉ L1}
• Rozdíl jazyků: L = L1 / L2
  L = {𝑤| 𝑤 ∈ ∑∗ ∧ 𝑤 ∈ L1 ∧ 𝑤 ∉ L2 }
• Zřetězení jazyků: L = L1 ⋅ L2 = L1 L2
  L = {𝑤| 𝑤 ∈ ∑∗ ∧ 𝑤 = 𝑢 ⋅ 𝑣 ∧ 𝑢 ∈ L1 ∧ 𝑣 ∈ L2 }

Question 9

Jazyk akceptovaný automatem

Answer 9

Množina všech řetězců, které automat
převedou z počátečního stavu do některého ze stavů koncových

Question 10

Definice gramatiky

Answer 10

Gramatika je uspořádaná čtveřice G = (N, T, S, P) , kde
N …….. množina neterminálních symbolů
T …….. množina terminálních symbolů
N ∩ T = ∅
S ∈ N …. počáteční symbol
P …………. množina přepisovacích pravidel ve tvaru a ⟶ b
kde a ∈ (N ∪ T)* N (N ∪ T)*
b ∈ (N ∪ T)*

Question 11

Jazyk generovaný gramatikou

Answer 11

Jazykem generovaným gramatikou G rozumíme množinu všech terminálních řetězců, které lze v gramatice odvodit z počátečního symbolu

Question 12

Chomského klasifikace – gramatiky typu 0

Answer 12

všechna pravidla jsou ve tvaru a ⟶ b , kde
a ∈ (N ∪ T)* N (N ∪ T)*
b ∈ (N ∪ T)*

Question 13

Chomského klasifikace – gramatiky typu 1

Answer 13

• všechna pravidla jsou ve tvaru a X b ⟶ a Y b , kde
  a, b ∈ (N ∪ T)*
  X ∈ N
  Y ∈ (N ∪ T)+
  Výjimka: v gramatice může být pravidlo S ⟶ e, pak se ovšem S nesmí vyskytnout na pravé straně přepisovacích pravidel
• používané názvy – kontextová gramatika, context sensitive grammar (CSG), nevypouštěcí gramatika

Question 14

Chomského klasifikace – gramatiky typu 2

Answer 14

• všechna pravidla jsou ve tvaru X ⟶ Y , kde
  X ∈ N
  Y ∈ (N ∪ T)*
• používané názvy – bezkontextová gramatika (BKG), context free grammar (CFG)

Question 15

Chomského klasifikace – gramatiky typu 3P

Answer 15

všechna pravidla jsou ve tvaru X ⟶ w nebo X ⟶ w Y kde
X , Y ∈ N , w ∈ T*

Question 16

Chomského klasifikace – gramatiky typu 3L

Answer 16

všechna pravidla jsou ve tvaru X ⟶ w nebo X ⟶ Y w kde
X , Y ∈ N , w ∈ T*

Question 17

Jak se říká jazykům typu 0 a jaký je jejich syntaktický analyzátor?

Answer 17

Rekurzivně vyčíslitelné jazyky - Turingův stroj.

Question 18

Jak se říká jazykům typu 1 a jaký je jejich syntaktický analyzátor?

Answer 18

Kontextové jazyky - Lineárně omezený Turingův stroj.

Question 19

Jak se říká jazykům typu 2 a jaký je jejich syntaktický analyzátor?

Answer 19

Nedeterministický zásobníkový automat.

Question 20

Jak se říká jazykům typu 3 a jaký je jejich syntaktický analyzátor?

Answer 20

Regulární jazyky -Konečný automat.