0 Daumen
67 Aufrufe

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\}^{*} \)

von

Hallo,

hast du diese Aufgabe schon mal gelöst .

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

1 Antwort

0 Daumen

\(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.

von 2,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community