[NTIN071] Automaty a gramatiky
Materiály
Prof. Václav Koubek: Skripta pro přednášku Automaty a gramatikyMichal 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.
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$).
$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ů:
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ů:
- $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$
- $\delta ' \left( q_s, \lambda \right) = \left \lbrace \left[\delta \left(q_0, \sigma \right) , \sigma \right] : \sigma \in \Sigma \right \rbrace$
- $\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$
- Přidáme $q_f$ k $\delta ' \left( \left[r, \sigma \right], \sigma \right), \forall r \in F, \forall \sigma \in \Sigma$