0 Daumen
422 Aufrufe


Beweisen oder widerlegen Sie:
(a) Es gibt Grammatiken, die zwar nicht rechtslinear sind, die aber äquivalent zu einer rechtslinearen Grammatik sind, d.h. die erzeugten Sprachen sind gleich.
(b) Das Komplement von \( L=\left\{b^{n} a^{4 n} \mid n \in \mathbb{N}\right\} \) über \( \Sigma=\{a, b\} \) ist kontextfrei aber nicht regulär.
(c) Das Komplement von \( \left\{b^{n} a^{2 n} c^{n} \mid n \in \mathbb{N}\right\} \) über \( \Sigma=\{a, b, c\} \) ist nicht kontextfrei.
(d) Seien \( L_{1} \subseteq L_{2} \) und \( L_{2} \subseteq L_{3} \) Sprachen.
1. Ist \( L_{1} \) nicht regulär, so ist auch \( L_{3} \) nicht regulär.
2. Ist \( L_{3} \) nicht kontextfrei, so ist auch \( L_{2} \) nicht kontextfrei.
(Hinweis: Als Gegenbeispiele dienen oft Sprachen über dem Alphabet \( \{a\} \), insbesondere \( L_{\text {prim }}=\left\{a^{p} \mid p\right. \) Primzahl \( \left.\}.\right) \)
Avatar von

1 Antwort

0 Daumen

(a) Füge eine Regel hinzu, die die Sprache nicht verändert.

(b) Gib einen Kellerautomaten für \(L\) an. Baue daraus einen Kellerautomaten für das Komplement von \(L\). Außerdem Pumpinglemma um Regularität zu widerlegen.

(c) Pumpinglemma für kontextfreie Sprachen.

(d)

    1. \(\Sigma^*\) ist regulär

  2. Jede endliche Sprache ist kontextfrei.

Avatar von 5,7 k

" 2. Jede endliche Sprache ist kontextfrei." -- Das habe ich noch nicht Verstanden.

Der Automat

---> (q1) ---a---> (q2) ---b--->((q3))
|
+-----b---> (q3) ---a--->((q4))

erkennt nur die Wörter ab und ba.

Äuf ähnliche Weise kann man zu jeder endlichen Menge einen Automaten konstruieren, der genau die Wörter dieser Menge erkennt.

Also ist jede endliche Sprache regulär.

Weil jede reguläre Sprache kontextfrei ist, ist jede endliche Sprache kontextfrei.

ich verstehe nich wie mir das bei "2. Ist \( L_{3} \) nicht kontextfrei, so ist auch \( L_{2} \) nicht kontextfrei." und \( L_{2} \subseteq L_{3} \) helfen soll

Es gibt eine endliche Teilmenge von \(L_3\).

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community