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

Avatar von

Hallo,

hast du diese Aufgabe schon mal gelöst .

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

1 Antwort

0 Daumen
 
Beste Antwort

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

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community