Automaty a gramatiky

Formální jazyky

Abeceda

• značíme $\Sigma$
• množina symbolů (znaků)
• musí být konečná
• prázdná abeceda $\emptyset$
• např. $\Sigma = \{a, b, c\}$
  $\Sigma = \{0, 1\}$
  $\Sigma = \{\text{if}, \text{else}, \text{while}, \text{for}\}$

Řetězec (slovo)

• konečná posloupnost symbolů z $\Sigma$
• např. pro $\Sigma = \{a, b, c\}$
  $\varepsilon$, $a$, $ab$, $abcaacacccacc$ jsou řetězce
• $\varepsilon$ — prázdný řetězec
• $\Sigma^*$ — množina všech řetězců nad $\Sigma$
• $\Sigma^+$ — množina všech neprázdných řetězců nad $\Sigma$, tedy $\Sigma^+ = \Sigma^* - \{\varepsilon\}$
• např. $\Sigma^* = \{\varepsilon, a, b, c, aa, ab, ac, ..., aaa, ...\}$

Zřetězení

• zřetězení dvou řetězců $x$ a $y$ značíme $xy$
• platí $\varepsilon \cdot x = x \cdot \varepsilon = x$
• platí $(xy)z = x(yz)$
• platí $xy \neq yx$

Délka řetězce

• délka řetězce $x$ značíme $|x|$
• platí $|\varepsilon| = 0$
• platí $|x| = 1$ pro $x \in \Sigma$
• platí $|xy| = |x| + |y|$
• opakování symbolu:
• $a^3 = aaa$ nad $\Sigma = \{a, b, c\}$
• $a^0 = \varepsilon$ nad $\Sigma = \{a, b, c\}$

Reverzní řetězec

• reverzní řetězec $x$ značíme $x^R$
• platí $\varepsilon^R = \varepsilon$
• platí $abbbcbca^R = acbcbbba$ nad $\Sigma = \{a, b, c\}$

Podřetězec

• $x$ je podřetězec řetězce $w$ pokud platí
• $w = yxz$ pro $w, x, y, z \in \Sigma^*$
• např. nad $\Sigma = \{a, b, c\}$:
• $abba$ je podřetězec $aaaaabbaaaa$
• $ccc$ je podřetězec $ccc$

Podsekvence

• $x = x_1x_2...x_n$ je podsekvence řetězce $w$ pokud platí
• $x_1, x_2, ..., x_n \in \Sigma$
• $w = y_1x_1y_2x_2...y_nx_ny_{n+1}$
• $w, x, y_1, y_2, ..., y_{n+1} \in \Sigma^*$

Formální jazyk

• značíme $L$ a je definován nad abecedou $\Sigma$
• je množina řetězců nad $\Sigma$
• např. $L = \{abc, bca, bbb\}$ nad $\Sigma = \{a, b, c\}$
• můžeme zapisovat i jako definicí pomocí vlastnosti
• např.
  $L = \{w \in \Sigma^*\ |\ w \text{ obsahuje min. jedno } a\}$
  $L = \{ 1^n0^n\ |\ n \geq 0 \}$ nad $\Sigma = \{0, 1\}$
  $L = \{ w : w \in \{abb, cca\}^* \land |w| \mod 2 = 0 \}$ nad $\Sigma = \{abb, cca\}$

Jazyky

Práce

Pro následující množiny řetězců zapište definici jazyka pomocí vlastnosti:

• $L_1 = \{0101, 010101, 01010101, ...\}$
  nad $\Sigma = \{0, 1\}$
• $L_2 = \{3, 5, 7, 9, 11, ...\}$ nad $\Sigma = \mathbb{N}$
• $L_3 = \{2, 3, 5, 7, 11, ...\}$ nad $\Sigma = \mathbb{N}$
• $L_4 = \{aaab, bbaaa, baaba, bbabbaaaaa,\\bba, bb, abbaabb, ...\}$ nad $\Sigma = \{a, b\}$

Operace nad jazyky

• sjednocení — $L_1 \cup L_2 = \{w\ |\ w \in L_1 \lor w \in L_2\}$
• průnik — $L_1 \cap L_2 = \{w\ |\ w \in L_1 \land w \in L_2\}$
• rozdíl — $L_1 \setminus L_2 = \{w\ |\ w \in L_1 \land w \notin L_2\}$
• doplňek — $\overline{L} = \Sigma^* \setminus L$
• součin — $L_1L_2 = \{w_1w_2\ |\ w_1 \in L_1 \land w_2 \in L_2\}$
• iterace — $L^* = \bigcup_{i=0}^{\infty} L^i$

Operace nad jazyky

Práce

Pro následující jazyky proveďte následující operace:

• $L_1 = \{a, b, c\}$, $L_2 = \{b, c, d, e\}$
  nad $\Sigma = \{a, b, c, d, e\}$
• $L_1 \cup L_2$,   $L_1 \cap L_2$
• $L_1 \setminus L_2$,   $L_2 \setminus L_1$
• $L_1L_2$,   $L_1^*$
• $(L_1 \cup L_2)^*$
• $(\overline{L_1} \cup L_2)L_1$

Klasifikace formálních jazyků

• regulární jazyky
• bezkontextové jazyky
• kontextové jazyky
• rekurzivně spočetné jazyky
• formální jazyky

Regulární jazyky

• dají se popsat regulárními výrazy
• dají se popsat konečnými automaty
• dají se popsat regulárními gramatikami

Gramatiky

Gramatika

• gramatika je prostředek pro popis jazyka
• gramatika je čtveřice $G = (N, \Sigma, P, S)$, kde:
• $N$ je konečná množina neterminálů (v podstatě proměnné)
• $\Sigma$ je konečná množina terminálů ($N \cap \Sigma = \emptyset$)
• $P$ je konečná množina pravidel tvaru:
  $\alpha A \beta \rightarrow \gamma$, kde  $\alpha, \beta, \gamma \in (N \cup \Sigma)^*$ a
  $A \in N$
• $S \in N$ je počáteční symbol

Ukázka gramatiky

$G = (\{S, A, B\}, \{a, b\}, P, S)$, kde:

$P = \{ \\ S \rightarrow abA, \\ A \rightarrow aA\ |\ bB, \\ B \rightarrow aB\ |\ b \\ \}$

$L_G = \{abbb, ababaaaaab, ...\} = \{aba^nba^mb\ |\ n, m \geq 0\}$

Rozdělení gramatik

• regulární gramatiky
• bezkontextové gramatiky
• kontextové gramatiky
• neomezené gramatiky

Regulární gramatiky

• $G = (N, \Sigma, P, S)$ je regulární, pokud:
• všechna pravidla mají tvar
  $A \rightarrow aB$ nebo
  $A \rightarrow a$, kde $A, B \in N$ a $a \in \Sigma$
• neexistuje pravidlo, které by na pravé straně obsahovalo $S$, pak může:
• obsahovat pravidlo $S \rightarrow \varepsilon$

Neomezené gramatiky

• splňují podmínky gramatiky

Rozeznávání gramatik 1

Rozeznejte, zda je gramatika regulární či neomezená. Popište jazyk, který tato gramatika generuje.

Rozeznávání gramatik 2

Rozeznejte, zda je gramatika regulární či neomezená. Popište jazyk, který tato gramatika generuje.

Tvorba gramatik pro jazyky

Tvorba gramatik pro jazyky

• gramatika pro jazyk $L = \{a^nb^m\ |\ n, m \geq 0\}$
• řetězce, které generuje: $ab, aabbbbb, bbbbb, ...$
• obsahuje $\varepsilon$
• určíme známé: $G = (\{S, \dots\}, \{a, b\}, P, S)$
• neterminály budeme určovat podle abecedy

$L = \{a^nb^m\ |\ n, m \geq 0\} = \{\varepsilon, a, b, ab, aabbbbb, bbbbb, ...\}$

• startovní symbol musí generovat $\varepsilon$
• — $S \rightarrow \varepsilon$
• po začátku můžeme generovat $a$
• — $S \rightarrow aA$
• po $a$ můžeme generovat $a$
• — $A \rightarrow aA$
• po začátku můžeme generovat $b$

$L = \{a^nb^m\ |\ n, m \geq 0\} = \{\varepsilon, a, b, ab, aabbbbb, bbbbb, ...\}$

• — $S \rightarrow bB$
• po $b$ můžeme generovat $b$
• — $B \rightarrow bB$
• po $a$ můžeme generovat $b$
• — $A \rightarrow bB$
• po $a$ či $b$ můžeme ukončit již jedním symbolem
• — $A \rightarrow a$
• — $B \rightarrow b$

$L = \{a^nb^m\ |\ n, m \geq 0\} = \{\varepsilon, a, b, ab, aabbbbb, bbbbb, ...\}$

$G = (\{S, A, B\}, \{a, b\}, P, S)$, kde:

$P = \{ \\ S \rightarrow \varepsilon\ |\ aA\ |\ bB, \\ A \rightarrow aA\ |\ bB\ |\ a, \\ B \rightarrow bB\ |\ b \\ \}$

Automaty

Automaty

• slouží k rozpoznávání jazyků
• přijímají vstupní řetězec
• přecházejí mezi stavy pomocí přechodové funkce
• přechodová funkce je definována pro vstupní symbol a cílový stav
• přechodem do koncového stavu a přečtením celého vstupu přijímá řetězec

Konečné automaty

• řídící jednotka — řídí běh automatu
• stavy a přechodová funkce
• vstupní páska — obsahuje vstupní řetězec, dá se pouze číst
• hlava — čte symboly z pásky
• v každém kroku čtecí hlava přečte jeden symbol a přejde do dalšího stavu dle přechodové funkce

Definice konečného automatu

• $M = (Q, \Sigma, \delta, q_0, F)$, kde:
• $Q$ je konečná množina stavů
• $\Sigma$ je konečná vstupní abeceda
• $\delta$ je přechodová funkce
  $(q \in Q, a \in \Sigma) \rightarrow (v \in Q)$
• $q_0$ je počáteční stav, $q_0 \in Q$
• $F$ je množina koncových stavů, $F \subseteq Q$

Reprezentace KA

• pomocí přechodové funkce
• tabulkou
• graficky

Přechodová funkce

$M = (\{q_0, q_1, q_2\}, \{a, b\}, \delta, q_0, \{q_2\})$

$\delta(q_0, a) = q_1$

$\delta(q_1, b) = q_2$

$\delta(q_2, a) = q_2$

$\delta(q_2, b) = q_2$

$L = \{ab, abaaaa, ababbba, ...\}$ — musí začínat $ab$

Tabulka

$L = \{ b^na^mbk\ |\ n \geq 0, m \geq 0, k \in \{a, b\}^* \}$

Graf

ohodnocený orientovaný graf

graph RL
    start
    q0(((q0)))
    q1((q1))
    q2(((q2)))
    q0 -->| a | q1
    q0 -->| b | q0
    q1 -->| a | q1
    q1 -->| b | q2
    q2 -->| a | q2
    q2 -->| b | q2
    
    start --> q0
    
    style start fill:#00000000,stroke:#00000000,color:#fff
    style q2 stroke-width:3px
    style q0 stroke-width:3px
                

$L = \{ \varepsilon \cup b^na^mbk\ |\ n \geq 0, m \geq 1,\\k \in \{a, b\}^* \}$

Deterministický konečný automat

• pravidla definována dle přechodové funkce výše, tedy:
• $(q \in Q, a \in \Sigma) \rightarrow (v \in Q)$
• pro stav a symbol existuje právě jeden přechod
• pokud je pro každý stav a symbol definován přechod, pak se jedná o úplně určený deterministický konečný automat

Nederministický konečný automat

• pravidla definována dle přechodové funkce níže:
• $(q \in Q, a \in \Sigma) \rightarrow (v \subseteq Q)$
• pro stav a symbol si lze vybrat stav, do kterého se přejde
• pokud je pro každý stav a symbol definován přechod a množina je neprázdná, jedná se o úplně určený nedeterministický konečný automat

NKA

graph LR
    start
    q0(((q0)))
    q1((q1))
    q2(((q2)))
    q0 -->| a | q1
    q0 -->| b | q0
    q1 -->| a | q1
    q1 -->| b | q1
    q1 -->| a | q2
    q1 -->| b | q2
    q2 -->| a | q2
    q2 -->| b | q2
    
    start --> q0
    
    style start fill:#00000000,stroke:#00000000,color:#fff
    style q2 stroke-width:3px
    style q0 stroke-width:3px
                

epsilon-přechod

• speciální přechod v NKA
• přechod, který se může provést bez vstupu symbolu
• do množiny stavů přechodové funkce se přidá $\varepsilon$

NKA s epsilon-přechody

graph LR
    start
    q0(((q0)))
    q1((q1))
    q2(((q2)))
    q0 -->| a | q1
    q0 -->| b | q0
    q1 -->| a | q1
    q1 -->| b | q1
    q1 -->| a | q2
    q1 -->| b | q2
    q2 -->| a | q2
    q2 -->| b | q2
    q0 -->| ε | q2
    
    start --> q0
    
    style start fill:#00000000,stroke:#00000000,color:#fff
    style q2 stroke-width:3px
    style q0 stroke-width:3px
                

Více počátečních stavů

• speciální chování pro NKA
• místo jednoho počátečního stavu jich může být více
• přijímá se slovo, pokud existuje cesta z některého počátečního stavu do koncového

NKA s více počátečními stavy

graph LR
    start1
    start2
    q0(((q0)))
    q1((q1))
    q2(((q2)))
    q0 -->| a | q1
    q0 -->| b | q0
    q1 -->| a | q1
    q1 -->| b | q2
    
    start1 --> q0
    start2 --> q1
    
    style start1 fill:#00000000,stroke:#00000000,color:#fff
    style start2 fill:#00000000,stroke:#00000000,color:#fff
    style q2 stroke-width:3px
    style q0 stroke-width:3px
                

Ekvivalentní automaty

• automaty, které přijímají stejný jazyk
• pro každý NKA existuje ekvivalentní DKA
• každý DKA je možné převést na úplně určený DKA
• každý DKA lze minimalizovat
• pokud automaty přijímají stejný jazyk, je jejich minimální automat stejný až na označení stavů

Příklady

Jazyk na automat

Práce

Následující jazyky převeďte na DKA/NKA:

• $L_1 = \{a^nb^m | n, m \geq 0\}$
• $L_2 = \{ w | w \in \{0,1\} \land \text{obsahuje max. dva symboly 1}\}$
• $L_3 = \{ w | w \in \{0,1\} \land \text{nezačíná řetězcem 011}\}$
• $L_4 = \{ w | w \in \{0,1\} \land \text{neobsahuje dva symboly}\\\text{1 za sebou}\}$
• $L_5 = \{ kocka^{2n}pes^{3m} | n, m \geq 1\}$, $\Sigma = \{\text{kocka}, \text{pes}\}$

Další

• (již dříve) determinizace
• (již dříve) minimalizace
• skládání automatů (sjednocení, průnik, doplněk, ...)
• převody na gramatiky a regulární výrazy

Regulární výrazy

Regulární výraz

• nad abecedou $\Sigma$
• $\emptyset$, $\epsilon$, $a$ jsou regulární výrazy pro každé $a \in \Sigma$
• pokud $r$ a $s$ jsou regulární výrazy, pak i následující jsou regulární výrazy:
• $r + s$
• $rs$
• $r^*$

Ukázky RV

• $\Sigma = \{a, b\}$
• $a + b$
• $a^*b + b^*a$
• $(a + (b + \epsilon + bb)^*)^*$
• $\emptyset^*$

Priorita

1. iterace
2. řetezení
3. sjednocení

Je možné použít závorky.

Hodnota RV

• je regulární jazyk nad $\Sigma$, značíme $h(r)$
• $h(\emptyset) = \emptyset$
• $h(\epsilon) = \{\epsilon\}$
• $h(a) = \{a\}$, pro každé $a \in \Sigma$
• $h(r + s) = h(r) \cup h(s)$
• $h(rs) = h(r)h(s)$
• $h(r^*) = (h(r))^*$

Ukázky RV

• $\Sigma = \{a, b\}$
• $h(a + b) = \{a, b\}$
• $h(a^*b + b^*a) = \{ab, aab, b, ba, bba, bb, bbba, bbb, ...\}$
• $h((a + (b + \epsilon + bb)^*)^*) = \{ a, b \}^*$
• $h(\emptyset^*) = \{\epsilon\}$

Návrh RV k jazyku

• $L = \{ w | w \in \{a,b\}^* \land w \text{obsahuje podřetězec abba}\}$
• podřetězec = RV musí obsahovat abba = $abba$
• před a za může být cokoliv = $(a + b)^*$
• celý řetězec = $(a + b)^*abba(a + b)^*$

RV k jazyku

Práce

K následujícím jazykům navrhněte regulární výrazy:

• $L_1 = \{ w | w \in \{a,b\}^* \land \text{počet}\ a\ \text{je dělitelný}\ 3\ \text{bezezbytku} \}$
• $L_2 = \{ w | w \in \{a,b\}^* \land \text{neobsahuje podřetězec aa}\}$

Úpravy RV

Ekvivalentní úpravy RV, které nezmění hodnotu RV:

Zjednodušení RV

Práce

Zjednodušte následující RV:

• $V_1 = 0^*(0^*+1^*)$
• $V_2 = 11^* + 0^*0 + \varepsilon$
• $V_3 = (a + b)(b + \varepsilon)$
• $V_4 = (a^*\emptyset^*c+b^*a\varepsilon^*)^*(b+\emptyset+a\emptyset)^*$

Převody

• RV $\rightarrow$ KA
• KA $\rightarrow$ RV
• RG $\rightarrow$ RV
• RV $\rightarrow$ RG
• RG $\rightarrow$ KA
• KA $\rightarrow$ RG

jedná se o desítky algoritmů

Turingův stroj

Turingův stroj

• přijímají rekurzivně spočetné jazyky
• (ne)deterministické
• čtení a zápis na pásky
• nekonečná páska

Více o TS

Práce

Najděte si další zdroje o TS. K čemu se používají?

Třídy složitosti

Práce

Zjistěte, co jsou to třídy složitosti a jak se váží k TS.

Dokažte, zda platí $P = NP$.