0 Daumen
114 Aufrufe

Wo genau liegen die folgenden Sprachen in der Chomsky Hierarchie (sei \( \Sigma= \) \( \{a, b, c, d\}) \) ? Beweisen Sie Ihre Antworten. Geben Sie einen PDA an, falls die jeweilige Sprache kontextfrei ist, und erklären Sie diesen.
(a) \( L_{a}=\left\{b^{m} a^{n} \mid m, n \in \mathbb{N}, m \neq n\right\} \)
(b) \( L_{b}=\left\{a^{2 n} b^{2 n} c^{2 n} \mid n \in \mathbb{N}\right. \) und \( \left.200<n<200000\right\} \)
(c) \( L_{c}=\left\{w c^{n} b^{n} w^{R} \mid w \in\{a, d\}^{*}, n \in \mathbb{N}\right\} \)
(d) \( L_{d}=\left\{w \in\{a, b, c\}^{*} \mid \#_{c}(w)<\#_{b}(w)<\#_{a}(w)\right\} \)

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community