0 Daumen
23 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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community