Jsou následující bezkontextové gramatiky bez cyklů? U každé z gramatik rozhodněte, zdali ano (✔) či ne (✖).

Jsou následující bezkontextové gramatiky v normálním tvaru podle Chomského? U každé z gramatik rozhodněte, zdali ano (✔) či ne (✖).

Jsou následující bezkontextové gramatiky v normálním tvaru podle Chomského? U každé z gramatik rozhodněte, zdali ano (✔) či ne (✖):

Mějme dvě regulární gramatiky \(G_1\) a \(G_2\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Mějme dva úplně určené nedeterministické konečné automaty (tj. bez \(\varepsilon\)-přechodů a s jedním počátečním stavem) \(A_1\) a \(B_1\). Automat \(A_1\) má \(n\) stavů a automat \(B_1\) má \(m\) stavů, \(n \geq m\). Po determinizaci automatu \(A_1\) a následné minimalizaci dostaneme automat \(A_2\). Po determinizaci automatu \(B_1\) a následné minimalizaci dostaneme automat \(B_2\). Platí, že \(A_2\) i \(B_2\) jsou úplně určené. O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Mějme konečný automat \(M = (Q, \Sigma, \delta, q_0, F)\), kde \(L(M) = \emptyset\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Mějme následující dva deterministické konečné automaty \(M_1\), \(M_2\) (se stejnou množinou stavů \(Q\)): \[M_1 = (Q, \Sigma, \delta_1, q_1, F_1)\] \[M_2 = (Q, \Sigma, \delta_2, q_2, F_2)\] Dále mějme konečný automat \(M_3\) s více počátečními stavy (též se stejnou množinou stavů \(Q\)): \[M_3 = (Q, \Sigma, \delta_1 \cup \delta_2, \{q_1\} \cup \{q_2\}, F_1 \cup F_2)\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Mějme následující dva nedeterministické konečné automaty (bez \(\varepsilon\)-přechodů) \(M_1, M_2\), kde \(Q_1 \cap Q_2 = \emptyset\): \[M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)\] \[M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)\] Dále uvažujte následující konečný automat \(M_3\): \[M_3 = (Q_1 \times Q_2, \Sigma, \delta, (q_1, q_2), F_1 \times F_2)\] kde pro \(\forall c \in \Sigma, \forall (q_a, q_b) \in Q_1 \times Q_2\): \[\delta((q_a, q_b), c) = \{ (p_1, p_2) : p_1 \in \delta_1(q_a, c) \land p_2 \in \delta_2(q_b, c)\}\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), či nepravdivé (✖):

Mějme následující jazyk \(L\) nad abecedou \(\Sigma = \{\mathtt{a}\}\): \[L = \{\mathtt{a}^n: n\text{ je prvočíslo} \wedge 12 < n < 48\}\] Dále uvažujte následující tvrzení \(T\): \[(\exists p \geq 1)(\forall w \in L)[|w| \geq p \implies \] \[(\exists x,y,z \in \Sigma^*)(w = xyz \wedge |xy| \leq p \wedge |y| \geq 1 \wedge (\forall k \geq 0) xy^kz \in L)]\] Určete nejmenší možnou konstantu \(p\) tak, aby tvrzení \(T\) pro daný jazyk \(L\) dále platilo. (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.)

Mějme následující jazyk \(L\): \[L= \{\mathtt{0}^m u^m : m \in \mathbb{N} \wedge m > 1 \wedge u \in \{\mathtt{0},\mathtt{1},\mathtt{2}\}\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔) či ne (✖).

Mějme následující jazyk \(L\): \[L= \{\mathtt{c}^m \mathtt{a}^n \mathtt{b}^n : m,n \in \mathbb{N}_0\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔) či ne (✖).

Mějme následující jazyk \(L\): \[L= \{vuv^\mathrm{R} : v \in \{\mathtt{0},\mathtt{1}\}^* \wedge u \in \{\mathtt{2}\}^*\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔) či ne (✖).

Mějme následující jazyk \(L\): \[L= \{vv : v \in \{\mathtt{0},\mathtt{1}\}^*\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔), nebo ne (✖).

Mějme následující jazyk \(L\): \[L= \{vv^\mathrm{R} : v \in \{\mathtt{0},\mathtt{1}\}^*\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔) či ne (✖).

Mějme následující jazyk \(L\): \[L= \{vv^\mathrm{R}uu^\mathrm{R} : v \in \{\mathtt{0},\mathtt{1}\}^* \wedge u \in \{\mathtt{2},\mathtt{3}\}^*\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔) či ne (✖).

Mějme následující jazyk \(L\): \[L=\{\mathtt{a}^m \mathtt{b}^n : m,n \in \mathbb{N} \land 2 \leq m < n\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔) či ne (✖).

Mějme následující jazyk \(L\): \[L=\{\mathtt{c}^jwuw^\mathrm{R} : w \in \{\mathtt{a}, \mathtt{b}\}^* \wedge u \in \{\mathtt{c}\}^* \wedge j = |u|\}\] Mohou být následující řetězce (kde \(p\) je konstanta pumping lemma) použity k úspěšnému důkazu, že \(L\) není regulární, pomocí pumping lemma? U každého řetězce rozhodněte, zdali ano (✔) či ne (✖).

Mějme následující jazyk \(L\): \[L = \{ \mathtt{0}^n : n \in \mathbb{N} \wedge n\text{ je prvočíslo} \} \cup \{ \mathtt{0}^n : n \in \mathbb{N} \wedge n \geq 10 \}\] Dále uvažujte následující tvrzení \(T\): \[(\exists p \geq 1)(\forall w \in L)[|w| \geq p \implies (\exists x,y,z \in \Sigma^*)(w = xyz \wedge |xy| \leq p \wedge |y| \geq 1 \wedge (\forall k \geq 0) xy^kz \in L)]\] Určete nejmenší možnou konstantu \(p\) tak, aby tvrzení \(T\) pro daný jazyk \(L\) dále platilo. (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.)

Mějme následující jazyk \(L\): \[L = \{\mathtt{00}, \mathtt{01}, \mathtt{001}, \mathtt{0101}\}\] Dále uvažujte následující tvrzení \(T\): \[(\exists p \geq 1)(\forall w \in L)[|w| \geq p \implies (\exists x,y,z \in \Sigma^*)(w = xyz \wedge |xy| \leq p \wedge |y| \geq 1 \wedge (\forall k \geq 0) xy^kz \in L)]\] Určete nejmenší možnou konstantu \(p\) tak, aby tvrzení \(T\) pro daný jazyk \(L\) dále platilo. (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.)

Mějme následující jazyk \(L\): \[L = \{\mathtt{a}^m \mathtt{b}^m : m \in \mathbb{N} \wedge m > 1\}\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖):

Mějme následující jazyk \(L\): \[L = \{\mathtt{a}^n \mathtt{b}^m : m,n \in \mathbb{N} \wedge m , n \geq 2\}\] Z následujících tvrzení vyberte všechna pravdivá:

Mějme následující jazyk \(L\): \[L = \{\mathtt{a}^n \mathtt{b}^m : n,m \in \mathbb{N} \land n, m > 1 \land n \neq m\}\] Z následujících tvrzení vyberte všechna pravdivá:

Mějme následující jazyk \(L\): \[L = \{\mathtt{a}^{n^2} : n \in \mathbb{N} \wedge n \geq 1 \wedge n < 12\}\] Dále uvažujte následující tvrzení \(T\): \[(\exists p \geq 1)(\forall w \in L)[|w| \geq p \implies (\exists x,y,z \in \Sigma^*)(w = xyz \wedge |xy| \leq p \wedge |y| \geq 1 \wedge (\forall k \geq 0) xy^kz \in L)]\] Určete nejmenší možnou konstantu \(p\) tak, aby tvrzení \(T\) pro daný jazyk \(L\) dále platilo. (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.)

Mějme následující jazyk: \[L = \{\mathtt{a}^{5k} : k \in \mathbb{N}_0\}\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Mějme následující jazyk: \[L = \{xux : x\in\{\mathtt{0}, \mathtt{1}\}^* \land u\in\{\mathtt{0}, \mathtt{1}\}\}\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Mějme následující konečný automat \(M\): \[M = (\{0,1,2,3,4\}, \{\mathtt{a}, \mathtt{b}\}, \delta, 0, \{2\})\] \[\begin{array}{r||c|c|c} \delta & \mathtt{a} & \mathtt{b} & \varepsilon\\\hline\hline \rightarrow 0 & \{0,1\} & \{0,3\} & \emptyset\\\hline 1 & \{2,4\} & \{0\} & \emptyset\\\hline \leftarrow 2 & \emptyset & \emptyset & \{3\}\\\hline 3 & \emptyset & \emptyset & \{4\}\\\hline 4 & \{2\} & \emptyset & \emptyset \end{array}\] Kolik stavů bude mít konečný automat \(M^\prime\) vzniklý jako výsledek algoritmu pro převod NKA s \(\varepsilon\)-přechody na NKA bez \(\varepsilon\)-přechodů pro \(M\)? (Algoritmus tak jak byl probíraný na přednášce bez použití jakýchkoli jiných úprav, převodů nebo algoritmů nad \(M\) nebo \(M^\prime\).) Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.

Mějme následující konečný automat \(M\): \[M = (\{A, B, C, D\}, \{\mathtt{0}, \mathtt{1}\}, \delta, A, \{C,D\})\] \[\begin{array}{r||c|c|c} \delta & \mathtt{0} & \mathtt{1} & \varepsilon\\\hline\hline \rightarrow A & \emptyset & \{A,B,D\} & \emptyset\\\hline B & \{A\} & \emptyset & \{C\}\\\hline \leftarrow C & \{B, C\} & \{C\} & \{D\}\\\hline \leftarrow D & \emptyset & \emptyset & \{C\} \end{array}\] Kolik stavů bude mít konečný automat \(M^\prime\) vzniklý jako výsledek algoritmu pro převod NKA s \(\varepsilon\)-přechody na NKA bez \(\varepsilon\)-přechodů pro \(M\)? (Algoritmus tak jak byl probíraný na přednášce bez použití jakýchkoli jiných úprav, převodů nebo algoritmů nad \(M\) nebo \(M^\prime\).) Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.

Mějme následující nedeterministický konečný automat \(M\): \[M = (Q, \Sigma, \delta, q_0, F)\] Dále uvažujte následující konečný automat \(M^\prime\), kde \(q_f \in F\): \[M^\prime = (Q, \Sigma, \delta^\prime, q_f, F)\] s takto definovanou přechodovou funkcí: \(\forall q \in Q, c \in \Sigma: \delta^\prime(q, c) = \delta(q, c)\), \(\forall q \in F : \delta^\prime(q, \varepsilon) = \{q_0\}\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), či nepravdivé (✖):

Mějme následující regulární výraz \(V\) nad abecedou \(\{\mathtt{a}, \mathtt{b}, \mathtt{c}\}\): \[V = (\mathtt{a}(\emptyset^* + \mathtt{b}) + \mathtt{c}\mathtt{b}^*)^*\mathtt{c}^*\] Kolik KONCOVÝCH stavů bude mít konečný automat \(M\), který vznikne použitím algoritmu pro konstrukci NKA pro daný regulární výraz – metody sousedů (Glushkov)? Uvažujte použití algoritmu na \(V\) v zadaném tvaru bez úprav \(V\) nebo vzniklého \(M\). (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.)

Mějme následující regulární výraz \(V\) nad abecedou \(\{\mathtt{a}, \mathtt{b}, \mathtt{c}\}\): \[V = \mathtt{c} + \mathtt{a}^*(\emptyset^*+\mathtt{b})(\mathtt{cc}+\mathtt{a}^*)\mathtt{b}^*\] Kolik KONCOVÝCH stavů bude mít konečný automat \(M\), který vznikne použitím algoritmu pro konstrukci NKA pro daný regulární výraz – metody sousedů (Glushkov)? Uvažujte použití algoritmu na \(V\) v zadaném tvaru bez úprav \(V\) nebo vzniklého \(M\). (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.)

Mějme následující regulární výraz \(V\) nad binární abecedou: \[V = (\mathtt{0}+\mathtt{1})^*\mathtt{0}(\mathtt{0}+\mathtt{1})^*\mathtt{0}(\mathtt{0}+\mathtt{1})^*\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Mějme níže uvedený deterministický konečný automat \(M\). \[M = (\{A,B\}, \{\mathtt{0}, \mathtt{1}\}, \delta, A, \{B\})\] \[\begin{array}{r|c|c} \delta & \mathtt{0} & \mathtt{1}\\\hline\hline \rightarrow A & B & A\\\hline \leftarrow B & B & B \end{array}\] Kolik stavů má minimální deterministický konečný automat \(M^\prime\) takový, že \(L(M^\prime) = (L(M))^*\) (přijímající iteraci jazyka \(L(M)\))? (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.)

Mějme níže uvedený minimální deterministický konečný automat \(M\). Uvažujte algoritmus na konstrukci DKA pro doplněk jazyka. Kolik stavů má konečný automat \(M^\prime\) přijímající doplněk \(L(M)\) zkonstruovaný pomocí tohoto algoritmu? (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.) \[M = (\{A, B, C, D, E, F\}, \{\mathtt{0}, \mathtt{1}\}, \delta, A, \{D,E,F\})\] \[\begin{array}{r|c|c} \delta & \mathtt{0} & \mathtt{1}\\\hline\hline \rightarrow A & B &\\\hline B & B & C\\\hline C & C & D\\\hline \leftarrow D & D & E\\\hline \leftarrow E & E & F\\\hline \leftarrow F & & F \end{array}\]

Mějme níže uvedený minimální deterministický konečný automat \(M\). Uvažujte algoritmus na konstrukci DKA pro doplněk jazyka. Kolik stavů má konečný automat \(M^\prime\) přijímající doplněk \(L(M)\) zkonstruovaný pomocí tohoto algoritmu? (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.) \[M = (\{A, B, C, D, E\}, \{\mathtt{0}, \mathtt{1}, \mathtt{2}\}, \delta, D, \{A, D\})\] \[\begin{array}{r|c|c} \delta & \mathtt{0} & \mathtt{1} & \mathtt{2}\\\hline\hline \leftarrow A & D & A & A\\\hline B & A & & D\\\hline C & D & A & A\\\hline \leftrightarrow D & E & E & E\\\hline E & & B & C \end{array}\]

Mějme níže uvedený nedeterministický konečný automat \(M\) s více počátečními stavy. Kolik počátečních stavů má ekvivalentní minimální deterministický konečný automat? (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.) \[M = (\{A, B, C, D, E\}, \{\mathtt{0}, \mathtt{1}\}, \delta, \{A, C\}, \{B, C\})\] \[\begin{array}{r||c|c} \delta & \mathtt{0} & \mathtt{1}\\\hline\hline \rightarrow A & \{B\} & \{D\}\\\hline \leftarrow B & \emptyset & \emptyset\\\hline \leftrightarrow C & \{C\} & \{D\}\\\hline D & \{E\} & \{C\}\\\hline E & \{D\} & \{E\} \end{array}\]

Mějme níže uvedený nedeterministický konečný automat \(M\) s více počátečními stavy. Kolik počátečních stavů má ekvivalentní minimální deterministický konečný automat? (Zadávejte pouze celé číslo v desítkové soustavě pomocí číslic bez zbytečných úvodních nul.) \[M = (\{A, B, C, D, E\}, \{\mathtt{0}, \mathtt{1}\}, \delta, \{A, D\}, \{B, C, D\})\] \[\begin{array}{r||c|c} \delta & \mathtt{0} & \mathtt{1}\\\hline\hline \rightarrow A & \{A\} & \{A, B\}\\\hline \leftarrow B & \emptyset & \{C\}\\\hline \leftarrow C & \emptyset & \emptyset\\\hline \leftrightarrow D & \{E\} & \{D\}\\\hline E & \{D\} & \{E\} \end{array}\]

Nechť \(G\) je bezkontextová gramatika. O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖):

Nechť \(L\) je neprázdný jazyk nad abecedou \(\Sigma\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖). (\(L^\mathrm{R}\) značí jazyk \(L^\mathrm{R}=\left\{w^\mathrm{R} : w \in L\right\}\). Pokud je \(L\) nekonečný jazyk, pak \(|L| = \infty\), přičemž \(\infty + \infty = \infty\).)

Nechť \(L_1 = \{\mathtt{00}, \mathtt{1}\}\). Uvažujte jazyk \(L = L_1^*\). O každém z následujících řetězců rozhodněte, zdali patří do \(L\) (✔), či nepatří do \(L\) (✖):

Nechť \(L_1,L_2\) jsou dva libovolné konečné jazyky. O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖). (\(|L|\) značí počet prvků množiny \(L\); pokud je \(L\) nekonečná množina, pak \(|L| = \infty\), přičemž \(\infty + \infty = \infty\).)

Nechť \(L_1,L_2\) jsou jazyky nad abecedou \(\Sigma=\{\mathtt{a}, \mathtt{b},\mathtt{c}\}\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖).

Nechť \(L_1,L_2\) jsou libovolné neprázdné jazyky nad abecedou \(\Sigma\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖). (\(L^\mathrm{R}\) značí jazyk \(L^\mathrm{R}=\left\{w^\mathrm{R} : w \in L\right\}\). Pokud je \(L\) nekonečný jazyk, pak \(|L| = \infty\), přičemž \(\infty + \infty = \infty\))

Nechť \(L_1\) a \(L_2\) jsou jazyky nad stejnou abecedou takové, že \(L_1 \subsetneq L_2\) (tj. \(L_1\) je podmnožinou \(L_2\) a \(L_1 \neq L_2\)). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Nechť \(L_K\) je libovolný konečný jazyk. O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Nechť \(PG = (N, \Sigma, D , R, S)\) je překladová gramatika a \(h_i\) je vstupní homomorfismus a \(h_o\) je výstupní homomorfismus \(PG\) (kde definičním oborem jsou všechny řetězce \(w \in (\Sigma \cup D)^*\) takové, že \(S \Rightarrow^* w\)) O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖).

Nechť \(PG = (N, \Sigma, D , R, S)\) je překladová gramatika. O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖).

Nechť \(V\) je regulární výraz nad neprázdnou abecedou \(\Sigma\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖):

Nechť \(n\in\mathbb{N}, n\geq 1\). Dále uvažujte konečný automat \(M_n=(Q_n,\Sigma,\delta ,1,F)\), kde \(\Sigma\) je neprázdná abeceda, \(Q_n = \{1,\ldots,n\}\) a \(\delta(k,a)=k + 1\) pro každé \(a\in \Sigma\) a \(1 \leq k \leq n - 1\), \(F=\{n\}\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖). (\(|X|\) značí počet prvků množiny \(X\).)

Nechť je dána bezkontextová gramatika \(G=(N,\Sigma,P,S)\) a zásobníkové automaty \(R_1,R_2\): \(R_1=(\{q\},\Sigma,N\cup \Sigma,\delta_1,q,S,\emptyset)\) kde \(\delta_1\): \[\begin{align*} &\forall A\in N: \delta_1(q,\varepsilon,A) = \{(q,\alpha) \mid (A\rightarrow \alpha) \in P \}\\& \forall a\in \Sigma: \delta_1(q,a,a) = \{(q,\varepsilon)\} \end{align*}\] \(R_2 = (\{q,r\},\Sigma,N\cup \Sigma\cup\{\#\}, \delta_2,q,\#,\{r\})\) kde \(\delta_2\): \[\begin{align*} &\forall a\in \Sigma: \delta_2(q,a,\varepsilon) = \{(q,a)\}\\&\delta_2(q,\varepsilon,\alpha) = \{(q,A)\mid (A\rightarrow \alpha)\in P\}\\&\delta_2(q,\varepsilon,\#S) = \{(r,\varepsilon)\} \end{align*}\] přičemž \(R_1\) přijímá prázdným zásobníkem a \(R_2\) přijímá přechodem do koncového stavu. O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖).

O každé z následujících \(n\)-tic rozhodněte, zdali splňuje (✔) či nesplňuje (✖) definici deterministického Turingova stroje:

O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖).

O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖):

O každém z následujících tvrzení rozhodněte, zdali patří (✔) či nepatří (✖) do množiny regulárních výrazů nad abecedou \(\Sigma\):

Uvažujme gramatiku \(G=(\{A,B,C,D,E,S\},\{a,b,c,d,e\},P,S)\), kde \[\begin{align*} P=\{& \\ &S \rightarrow A \mid B \mid C \mid D \mid E \mid S \\ &A \rightarrow a \\ &B \rightarrow b \\ &C \rightarrow c \\ &D \rightarrow d \\ &E \rightarrow e \\ \} \end{align*}\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖).

Uvažujme konečný automat \(M=(Q,\Sigma,\delta,1,F)\), kde \(Q=\{1,2,\ldots, 666\}\), \(\Sigma=\{\mathtt{x}, \mathtt{y}, \mathtt{z}, \mathtt{a}, \mathtt{b}, \mathtt{c}\}\), \(F=\{666\}\). Dále pro všechny \(a\in \Sigma\) platí, že pokud \(k<\ell\) pak: \[\delta(k,a)=\ell\] Kolik přechodů existuje v \(M\)?

Uvažujte algoritmus CYK (Cocke–Younger–Kasami). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖):

Uvažujte bezkontextovou gramatiku \(G = (N, \Sigma, P, S)\), kde \(\varepsilon \notin L(G)\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte bezkontextovou gramatiku \(G = (N, \Sigma, P, S)\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte gramatiku \(G\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte konečný automat \(M = (\{A,B,C,D\}, \{\mathtt{0}, \mathtt{1}\}, \delta, C, \{B\})\), kde \(\delta\) je popsána přechodovým diagramem níže. O každém z tvrzení níže rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖).

Uvažujte konečný automat \(M = (\{A,B\}, \{\mathtt{0}, \mathtt{1}\}, \delta, A, \emptyset)\), kde \(\delta\) je popsána přechodovým diagramem níže. O každém z tvrzení níže rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖).

Uvažujte metodu eliminací stavů pro převod konečného automatu \(M\) na regulární výraz \(V\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖) :

Uvažujte metodu sousedů (Glushkov) pro převod regulárního výrazu \(V\) na konečný automat \(M\). Uvažujte použití této metody bez jakýchkoli dalších úprav \(V\) nebo \(M\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující bezkontextovou gramatiku \(G\): \[G = (\{A, B, C\}, \{\mathtt{0}, \mathtt{1}, \mathtt{2}\}, P, C)\] \[ \begin{array}{l} P = \{\\ A \to BB\mathtt{0},\\ B \to \mathtt{0}BB\mathtt{1} \mid A\mathtt{1},\\ C \to \varepsilon \mid \mathtt{2} \mid \mathtt{1}A\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující dva formální jazyky nad abecedou \(\Sigma = \{\mathtt{0}\}\): \[L_1 = \{\mathtt{0}^n : n \in \mathbb{N}_0\}\] \[L_2 = \{\mathtt{0}^n \mathtt{0}^n : n \in \mathbb{N}_0\}\] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{A, B, C, D ,E\}, \{\mathtt{0}, \mathtt{1}\}, P, B)\] \[ \begin{array}{l} P = \{\\ A \to \varepsilon \mid \mathtt{0}B,\\ B \to \mathtt{0}B \mid \mathtt{1},\\ C \to \mathtt{1}D \mid \mathtt{0}\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{A, B, C\}, \{\mathtt{0}, \mathtt{1}\}, P, A)\] \[ \begin{array}{l} P = \{\\ A \to \varepsilon \mid \mathtt{0}B,\\ B \to C \mid \mathtt{0}B,\\ C \to \mathtt{1}\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{A, B, S\}, \{\mathtt{a}, \mathtt{b}, \mathtt{c}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to S\mathtt{a}S\mathtt{b} \mid \varepsilon\\ \} \end{array} \] Z následujících tvrzení vyberte všechna pravdivá:

Uvažujte následující gramatiku \(G\): \[G = (\{A, B\}, \{\mathtt{a}, \mathtt{b}, \mathtt{c}\}, P, A)\] \[ \begin{array}{l} P = \{\\ A \to B\mathtt{a} \mid \mathtt{b}A,\\ B \to \varepsilon\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{A, B\}, \{\mathtt{a}, \mathtt{b}, \mathtt{c}\}, P, A)\] \[ \begin{array}{l} P = \{\\ A \to \mathtt{b}A,\\ \mathtt{b}A \to \mathtt{b}B\mathtt{c},\\ B \to \varepsilon\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), či nepravdivé (✖).

Uvažujte následující gramatiku \(G\): \[G = (\{A, B\}, \{\mathtt{a}, \mathtt{c}\}, P, A)\] \[ \begin{array}{l} P = \{\\ A \to \mathtt{a}B \mid \varepsilon,\\ B \to \mathtt{c}\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{A, S\}, \{\mathtt{a}, \mathtt{b}, \mathtt{c}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to \mathtt{a}S \mid \mathtt{a}A,\\ A \to \mathtt{b}A \mid \mathtt{b},\\ SA \to \mathtt{c}\\ \} \end{array} \] Z následujících tvrzení vyberte všechna pravdivá:

Uvažujte následující gramatiku \(G\): \[G = (\{B, S\}, \{\mathtt{a}, \mathtt{b}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to \mathtt{a}S\mathtt{b} \mid B\\ B \to \mathtt{b}B \mid \varepsilon\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{S, A, B\}, \{\mathtt{1}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to \mathtt{1}B \mid A,\\ A \to B,\\ B \to S \mid \varepsilon\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{S, X, Y\}, \{\mathtt{a}, \mathtt{b}, \mathtt{c}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to \mathtt{a}S\mathtt{a} \mid XY\\ \mathtt{a}X \to X\mathtt{c} \mid \varepsilon\\ Y\mathtt{a} \to \mathtt{b}Y \mid \varepsilon\\ \} \end{array} \] Z následujících tvrzení vyberte všechna pravdivá:

Uvažujte následující gramatiku \(G\): \[G = (\{S, Z\}, \{\mathtt{0}, \mathtt{1}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to \varepsilon \mid \mathtt{0}Z \mid \mathtt{1},\\ \mathtt{0}S\mathtt{1} \to \mathtt{0}Z\mathtt{01}\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující gramatiku \(G\): \[G = (\{S\}, \{\mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{d}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to \varepsilon\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující metody. Pokud těmto metodám dáme na vstup deterministický konečný automat \(M\), vrátí pro něj regulární výraz \(V\) takový, že \(L(M) = h(V)\)? U každé z metod rozhodněte, zdali ano (✔) či ne (✖):

Uvažujte následující regulární výraz \(V\) nad abecedou \(\{\mathtt{a},\mathtt{b},\mathtt{c},\mathtt{d}\}\): \[V = \mathtt{a}^*\mathtt{b}(\mathtt{c}^*\mathtt{ba}^* + \mathtt{d})^* + \mathtt{d}^*\] Pro \(V\) spustíme metodu sousedů (Glushkov; uvažujte tuto metodu bez jakýchkoli úprav \(V\)). Kolik prvků budou obsahovat množiny \(Z\) (množina počátečních symbolů), \(F\) (množina koncových symbolů) a \(P\) (množina sousedů)? Odpověď zadejte ve formátu: \(|Z|\), \(|F|\), \(|P|\) (tj. tři desítková celá čísla oddělená čárkou a mezerou).

Uvažujte následující uspořádanou čtveřici \(G\): \[G = (\{S, A, B\}, \{\mathtt{1}\}, P, S)\] \[ \begin{array}{l} P = \{\\ S \to \mathtt{1} \mid A,\\ A \to B,\\ 1 \to BA\\ \} \end{array} \] O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte následující zásobníkový automat \(R = (\{A, B, C\}, \{\mathtt{0}\}, \{a, b\}, \delta, A, b, \{B\})\) přijímající přechodem do koncového stavu, který má vrchol zásobníku vlevo. O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte nedeterministický konečný automat \(M\) o \(n\) stavech. Tento automat převedeme na ekvivalentní minimální deterministický automat \(M'\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte nejlepší algoritmus \(A\) z přednášek, který o řetězci délky \(n\) a regulární gramatice \(G\) (jejíž velikost považujeme za konstantu) rozhodne, zda \(w \in L(G)\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔) či nepravdivé (✖):

Uvažujte regulární výraz \(V=\mathtt{a}^*\mathtt{a}\varepsilon+\mathtt{b}^*\varepsilon \mathtt{b}+\mathtt{ab}\emptyset \mathtt{ba}\) nad abecedou \(\Sigma = \{\mathtt{a}, \mathtt{b}\}\). O každém z následujících tvrzení rozhodněte, zdali je pravdivé (✔), nebo nepravdivé (✖). (\(V'\) označuje derivaci regulárního výrazu \(V\) podle řetězce \(\mathtt{aa}\). \(|w|_x\) označuje počet symbolů \(x\) v řetězci \(w\).)

Uvažujte syntaktickou analýzu pracující na základě bezkontextové gramatiky \(G = (N, \Sigma, P, S)\) pomocí zásobníkového automatu \(R = (\{q,r\}, \Sigma, N \cup \Sigma \cup \{Z_0\}, \delta, q, Z_0, \{r\})\) metodou zdola nahoru. O každém z následujících přechodů rozhodněte, zdali je (✔) či není (✖) součástí přechodové funkce automatu \(R\):