Zwei Fragen zu regulären und kontextfreien Sprachen

Question

Ich bin gerade dabei online meine Theoretische Informatik Klausur einzusehen, leider fehlen mir 2 Pkt. zum bestehen, da die Einsicht online stattfindet, kann ich leider keinen Übungsleiter o. Ä. wegen der Korrektur fragen. Daher hoffe ich einige Unklarheiten hier beantwortet zu bekommen. Bei der Aufgabe handelte es sich um ein Quiz zu Sprachen, wo kurze Ja/Nein Fragen begründet beantworten sollte:

1. Frage: Jede endliche Teilmenge einer kontextfreien Sprache ist kontextfrei.

Meine Antwort:  Korrekt, es gilt die Chomsky Hierarchie: $$Typ 0 \supset Typ 1 \supset Typ 2(kontextfrei) \supset Typ 3(regulär)$$ Somit ist jede Sprache A aus den kontextfreien Sprachen erneut kontextfrei.

Musterlösung: Korrekt. Jede endliche Menge ist sowieso regulär (und damit kontextfrei).

2. Frage: $$ \text { Seien } A , B \subseteq \Sigma ^ { * } \text { regulär mit } \varepsilon \notin A \text { . Dann sind alle Lösungen } X \subseteq  {\sum } ^ { * } \text { der Gleichung } X = A X \cup B . $$

Meine Antwort: X ist ebenfalls regulär und Regularität ist über dem Produkt und der Vereinigung abgeschlossen. (Mir ist im Nachhinein klar, dass diese Aufgabe auf das Ardens Lemma abzielte, aber meiner Meinung nach ist dieser Ansatz auch nicht falsch)

Musterlösung: Ja laut Ardens Lemma ist dann X = A*B, was regulär ist, da A und B regulär sind.

Jede der Fragen gibt einen Punkt, ich habe auf keine der beiden Antworten einen Punkt bekommen

Answer 1

Somit ist jede Sprache A aus den kontextfreien Sprachen erneut kontextfrei.

Hast du gerade behauptet, das jede kontextfreie Sprache kontextfrei ist?

... regulär (und damit kontextfrei)

Das gilt wegen der Chomsky Hierarchie. Trotzdem reicht ein Hinweis auf die Chomsky Hierarchie nicht als Begründung aus. Mir fehlt in deiner Begründung zum Beispiel ein Hinweis darauf, dass die Teilmenge endlich ist. Lässt man auch unendliche Teilmengen zu, dann gilt die Aussage nämlich nicht mehr.

Regularität ist über dem Produkt und der Vereinigung abgeschlossen

Das kannst du nur dann als Argument für die Regularität von X verwenden, wenn auf der rechten Seite der Gleichung (AX∪B) die Sprachen A, X und B regulär sind. Für A und B steht das in der Voraussetzung, für X aber nicht. Du müsstest also noch begründen, warum X regulär ist. Wie du siehst, drehst du dich im Kreis.

Comments

vielen Dank, dass war mir so nicht klar!