Begründen Sie Ihre Antworten, insbesondere, warum Ihre Grammatik von keinem größeren Typ ist.

Question

Frage:

Chomsky-Hierarchie
Geben Sie für folgende Sprachen jeweils (i) eine Grammatik \( G_{i} \) mit \( L\left(G_{i}\right)=L_{i}, 1 \leq i \leq \) 3 und möglichst großem Typ an und (ii) geben Sie explizit den maximalen Typ Ihrer Grammatik an. Begründen Sie Ihre Antworten, insbesondere, warum Ihre Grammatik von keinem größeren Typ ist.
(a) \( L_{1}=\left\{a^{n} b^{m} \mid n, m \geq 2\right\} \subseteq\{a, b\}^{*} \)
(b) \( L_{2}=\left\{a b a^{n+2} b a \mid n \geq 1\right\} \subseteq\{a, b\}^{*} \)
(c) \( L_{3}=\left\{0^{2 n} 110(01)^{n} \mid n \geq 0\right\} \subseteq\{0,1\}^{*} \)

Comments

Hallo,

hast du diese Aufgabe schon mal gelöst .

ich brächte auch die Lösung von dieser Aufgabe

Answer 1

\(L_1\) und \(L_2\) sind regulär.

\(L_3\) ist kontextfrei, weil \(L_3\) durch einen Kellerautomaten erkannt werden kann.

\(L_3\) ist nicht regulär, weil ein DEA nicht zählen kann, wie lang das 0-Präfix des Wortes ist, diese Information aber für das 01-Suffix benötigt wird.