[NTIN071] Automaty a gramatiky

Materiály

Prof. Václav Koubek: Skripta pro přednášku Automaty a gramatiky
Michal Chytil: Sbírka řešených příkladů z teorie automatů a formálních jazyků

Domácí úkoly

Cvičení 1 – 2.3.2017

$L = \left \lbrace a^p | p \text{ je prvočíslo} \right \rbrace$
Předpokládejme, že $L$ je regulární. Pak podle pumping lemma existuje $q \gt 0$ takové, že každá věta $a^p \in L$, kde $p \geq q$, může být zapsána ve tvaru $a^p = xyz$, $y \neq \epsilon$, $|xy| \leq q$, a platí $xy^iz \in L$ pro $i \geq 0$.
Zvolme $r$ provočíslo větší, než $q$. $a^r \in L$, $|a^r| = r$ a $r \geq q$, což implikuje $a^r = xyz$, $y \neq \epsilon$, $|xy| \leq q$, a platí $xy^iz \in L$ pro $i \geq 0$.
Nechť $|y| = k $ a zvolme $i = r + 1$. Potom ale $|xy^{r+1}z| = |xyz| + |y^r| = r + rk = r(k+1)$, což ale rozhodně není prvočíslo a tedy $xy^{r+1}\ \notin L$, což je spor.

Cvičení 3 - 16.3.2017

Pro každé $n \geq 1$ nalezněte jazyk $L_n$ takový, že každý deterministický automat rozpoznávající $L_n$ má aspoň $2^n$ stavů, a zároveň $L_n$ lze rozpoznat nedeterministickým automatem s $n$ stavy.
$L_n = \left\lbrace a b^* \left( \left( \left( a b^* \right) ^{n-1} \left( a^* b^* \right) ^* \right) | \left( \left( a^* b^* \right) ^* b \right) \right) \right\rbrace$
Nedeterministický automat, který by toto rozpoznával: uspořádejme si stavy $q_0$ až $q_{n-1}$ do vrcholů $n$-úhelníka. Označme $q_0$ vstupním a zároveň i výstupním stavem. Potom mezi každými dvěma stavy $q_i$ a $q_{i+1}$ existuje přechodová funkce pro symbol $a$, stejná existuje i pro dvojici $q_{n-1}$ a $q_0$ (jedním směrem po obvodu $n$-úhelníka). Zároveň z každého stavu kromě $q_0$ vede přechodová funkce pro symbol $b$ zpět do tohoto stavu a do stavu $q_0$ (úhlopříčky $n$-úhelníka do $q_0$).
Lehce můžeme nahlédnout, že jakákoliv podmnožina stavů při přeměně na DKA je dosažitelná (včetně $\emptyset$ – stačí vstoupit a jít po přechodové funkci pro symbol $b$).

Cvičení 4 - 23.3.2017

Dokažte či vyvraťte, že pro každý regulární jazyk $L$ je i následující jazyk regulární: $\text{shift}(L) = \left \lbrace uv | vu \in L \right \rbrace$
Předpokládejme, že je jazyk $L$ zadán DKA $M = \left( Q, \Sigma, \delta, q_0, F \right)$ tak, že platí $L = L(M)$. Zkonstuujeme NKA $N = \left(Q', \Sigma, \delta ', q_s, \left \lbrace q_f \right \rbrace \right)$ splňující, že $\text{shift}(L) = L(N)$ s $Q' = Q \times \Sigma \cup \left \lbrace q_, q_f \right \rbrace$ a $\delta '$ podle následujících kroků:
  1. $Q \times \Sigma = \left \lbrace \left[q, \sigma \right] : q \in Q, \sigma \in \Sigma \right \rbrace$, kde $\left[q, \sigma \right]$ je stav pro první symbol z řetězce v $L$, který je $\sigma$
  2. $\delta ' \left( q_s, \lambda \right) = \left \lbrace \left[\delta \left(q_0, \sigma \right) , \sigma \right] : \sigma \in \Sigma \right \rbrace$
  3. $\delta ' \left( \left[q, \sigma \right], \sigma ' \right) = \left \lbrace \left[\delta \left(q, \sigma ' \right) , \sigma \right] \right \rbrace, \forall q \in Q, \forall \sigma , \sigma ' \in \Sigma$
  4. Přidáme $q_f$ k $\delta ' \left( \left[r, \sigma \right], \sigma \right), \forall r \in F, \forall \sigma \in \Sigma$
Víme, že regularitu můžeme dokázat, můžeme-li pro jazyk zkonstruovat DKA nebo NKA. Toto se nám pro $\text{shift} (L) $ povedlo, proto operace $\text{shift} (L) $ zachovává regularitu.

Poslední aktualizace: 06. 04. 2017 09:39:37 CEST