Untitled Presentation

​TI25: Multiple Choice

By Ruben Oliveira Rodrigues

Multiple Select

Betrachte das Alphabet $$\left\{a,b\right\}$$ . Welche der folgenden Sprachen über dem Alphabet sind regulär?

• L₁ = {w∈{a,b}^* | w enthält das Teilwort ababab nicht.}

• L₁ = {w∈{a,b}^* | $$\left|w\right|_a\ge\ 64$$ und $$\left|w\right|_b=2\ \left(mod\ 5\right)$$ .}

• L₁ = {w∈{a,b}^* | $$\left|w\right|_a=0\ \left(mod\ \left|w\right|_b\right)$$ .}

• L₄ = {bⁿaw∈{a,b}^* | $$n\ \in\ N$$ w enthält das Teilwort bⁿ nicht.}

Multiple Select

Welche der folgenden Aussagen gilt für jede reguläre Sprache $$L\ne\ \left\{\right\}$$ über Σ_bool.

• Falls ein NEA mit 3 Zuständen existiert, welcher L akzeptiert, so gibt es auch einen deterministischen EA mit 8 Zuständen, der L akzeptiert.

• Sei $$n_0$$ die Konstante, so dass das Pumping Lemma gilt. Dann existiert $$w\in\ L$$ mit $$\left|w\right|<n_0$$ .

• Sei L'⊆Σ_bool^* endlich. Dann ist $$L\cup\ L'$$ regulär.

• Für jedes x∈Σ_bool^* definieren wir $$L_x\ =\ \left\{y\ \in\ \Sigma\ _{bool^{ }}^{\cdot}\left|\ xy\ \in\ L\right|\right\}$$ . Dann ist nach Lemma 3.3 die Familie von Sprachen $$\left\{L_x\ \left|\ x\in\ \Sigma\ _{bool^{ }}^{\cdot}\right|\right\}$$ endlich.

Multiple Select

Sie $$x_n=0^{3\cdot\lceil\ \log_2\left(n\right)\rceil\ }$$ eine folge von Wörtern über dem boolschen Alphabet und $$K\left(x_n\right)$$ deren Kolmogorov Komplexität. Welche der folgenden Aussagen sind korrekt?

• Es existiert eine Konstante $$c_1\in\ N$$ , sodass für alle $$n\in\ N^+$$

  $$K\left(x_n\right)\le\ \frac{1}{3}\left|x_n\right|+c_1$$

• Für alle N∈ℕ existier ein n≥N, so dass $$x_n$$ zufällig ist.

• Es existiert eine Konstante $$c_2\in\ N$$ , sodass für alle $$n\in\ N,\ n\ge2$$

  $$K\left(x_n\right)\le\ \log_2\left(\left|x_n\right|\right)+c_2$$

• Für alle $$c_3\in\ N$$ existiert ein N∈ℕ, sodass für alle n≥N gilt:

  $$K\left(x_n\right)>2^{\frac{1}{3}c_3}$$

• Für alle N∈ℕ existier ein n≥N, so dass:

  $$K\left(x_n\right)>\lceil\ \log_2\left(n\right)\rceil\$$