[NTIN071] Automaty a gramatiky
Zápočet
- prezence (při výrazné absenci bude náhradní domácí úloha)
- aktivita (body za nápady a vyřešené věci na tabuli)
- domácí úkoly (úlohy, které se nestihly na cvičení, odevzdávají se na papíře další hodinu)
- 2 písemky (před polovinou a před koncem semestru, hodnocení binární)
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 – 23.2.2016
Zadání:
- Sestrojte automat: $L = \left \lbrace w | w \in \left \lbrace a, b \right \rbrace ^* \wedge 2 \mid |w|_a \wedge 3 \nmid |w|_a \right \rbrace$
Počet $a$ je dělitelný 2 a zároveň počet $a$ není dělitelný 3. - Sestrojte konečný jazyk: $L = \left \lbrace w | w \in \left \lbrace a, b \right \rbrace ^* \wedge \text{ .*}abba \text{ .*} \left (\text{lze zapsat jako }w = u . abba . v \right ) \right \rbrace$
Slovo obsahuje $abba$. - Navrhněte konečné automaty, které přijímají slova, u nichž začátek souvisí s koncem: $L = \left \lbrace w | w \in \left \lbrace a, b \right \rbrace ^* \wedge \left ( \exists u, v, z \in \left \lbrace a, b \right \rbrace ^* \right ) \left ( |u| = 2 \wedge |z| = 2 \wedge w = u.v.z \wedge u \neq z \right )\right \rbrace $
Jazyk obsahuje slova, která mají délku aspoň 4 a začínají a končí různými (uspořádanými) dvojicemi symbolů.
Cvičení 2 – 1.3.2016
Zadání:
- Rozhodněte, zda je následující jazyk regulární: $L = \left \lbrace a^i b^j c^k | i, j, k = 0, 1, 2, \dots \wedge i \leq j \leq k \right \rbrace$
- Rozhodněte, zda je následující jazyk regulární: $L = \left \lbrace ww^R | w \in \left \lbrace a, b \right \rbrace ^* \right \rbrace$
Cvičení 3 – 8.3.2016
Zadání:
- Rozhodněte, zda je následující jazyk regulární: $L = \left \lbrace a^p | p \text{ je prvočíslo} \right \rbrace$
- Rozhodněte, zda je následující jazyk regulární: $L = \left \lbrace a^{i^3} | i \in \left \lbrace 0, 1, \dots \right \rbrace \right \rbrace$
Cvičení 4 – 15.3.2016
Zadání:
- Rozhodněte, zda jsou některé z následujících automatů po dvojicích ekvivalentní:
$\begin{array}{r|c|c} a) & a & b \\ \hline \longleftrightarrow 0 & 0 & 5 \\ \hline 1 & 1 & 3 \\ \hline 2 & 2 & 7 \\ \hline 3 & 3 & 2 \\ \hline \longleftarrow 4 & 4 & 1 \\ \hline 5 & 5 & 1 \\ \hline \longleftarrow 6 & 6 & 2 \\ \hline 7 & 7 & 0 \\ \hline \end{array}$$\begin{array}{r|c|c} b) & a & b \\ \hline A & A & F \\ \hline B & B & A \\ \hline C & C & D \\ \hline D & D & B \\ \hline E & E & C \\ \hline \longleftrightarrow F & F & E \\ \hline \end{array}$$\begin{array}{r|c|c} c) & a & b \\ \hline A & H & G \\ \hline B & B & A \\ \hline C & E & D \\ \hline D & D & B \\ \hline E & C & D \\ \hline F & F & E \\ \hline G & G & F \\ \hline \longleftrightarrow H & A & G \\ \hline \end{array}$$\begin{array}{r|c|c} d) & a & b \\ \hline \longrightarrow 1 & 2 & 3 \\ \hline 2 & 2 & 4 \\ \hline \longleftarrow 3 & 3 & 5 \\ \hline 4 & 2 & 7 \\ \hline \longleftarrow 5 & 6 & 3 \\ \hline \longleftarrow 6 & 6 & 6 \\ \hline 7 & 7 & 4 \\ \hline 8 & 2 & 3 \\ \hline 9 & 9 & 4 \\ \hline \end{array}$
- Zredukujte:
$\begin{array}{r|c|c} & a & b \\ \hline \longleftrightarrow \left \lbrace A,D \right \rbrace & \left \lbrace A,C \right \rbrace & \left \lbrace B,C,D \right \rbrace \\ \hline \longleftarrow \left \lbrace A,C \right \rbrace & \left \lbrace A,C \right \rbrace & \left \lbrace B \right \rbrace \\ \hline \longleftarrow \left \lbrace B,C,D \right \rbrace & \left \lbrace A,B,D \right \rbrace & \left \lbrace C,D \right \rbrace \\ \hline \longleftarrow \left \lbrace A,B,D \right \rbrace & \left \lbrace A,B,C,D \right \rbrace & \left \lbrace B,C,D \right \rbrace \\ \hline \longleftarrow \left \lbrace C,D \right \rbrace & \left \lbrace A \right \rbrace & \left \lbrace C,D \right \rbrace \\ \hline \left \lbrace B \right \rbrace & \left \lbrace B,D \right \rbrace & \emptyset \\ \hline \longleftarrow \left \lbrace A \right \rbrace & \left \lbrace A,C \right \rbrace & \left \lbrace B \right \rbrace \\ \hline \left \lbrace B,D \right \rbrace & \left \lbrace A,B,D \right \rbrace & \left \lbrace C,D \right \rbrace \\ \hline \emptyset & \emptyset & \emptyset \\ \hline \longleftarrow \left \lbrace A,B,C,D \right \rbrace & \left \lbrace A,B,C,D \right \rbrace & \left \lbrace B,C,D \right \rbrace \\ \hline \end{array}$
Cvičení 5 – 22.3.2016
I was too lazy to write it down.Cvičení 6 – 29.3.2016
- Přiřaďte regulární výraz na konečný automat, ověřte induktivním postupem.
- $ab+ba$
- $a^2 + b^2 + ab$
- $a + b^{*}$
- $\left (ab + c\right )^{*}$
- $\left (\left (ab+c\right )^{+} a\left (bc\right )^{*} + b\right )^{*}$
- $\left (\left (ab+c\right )^{*}a\left (bc\right )^{*}+b\right )^{*}$
- $\left (01^{*}+101\right )^{*}0^{*}1$
Cvičení 8 – 12.3.2016
-
Napište gramatiky k následujícím jazykům:
- $L_1 = \left \lbrace a^i b^j c^{i \cdot j} \right \rbrace$
- $L_2 = \left \lbrace a^i b^j c^{i^j} \right \rbrace$
- $L_3 = \left \lbrace a^{i^2} \right \rbrace$