Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in SPR-AE

Die Menge der konextfreien Sprachen ist gegenüber der Komplementbildung abgeschlossen.

Wed, 15 Jun 2016 17:01:36 +0000

In der Musterlösung steht als Erklärung, dass die Sprache
$$L = \{w \in \{0,1\}^\star\ | \ \forall u \in \{0,1\}^\star : w \neq uu\}$$
kontextfrei ist. Wieso ist das der Fall? Ich schaffe es nicht einen ndet Kellerautomat oder eine kontextfreie Grammatik zu schreiben, der/die das für alle Wörter überprüfen kann. Und könnte sie das wäre das Komplement doch auch kontextfrei?

DEA und NEA für $\emptyset$, $\lambda$ und $E^\star$

Sun, 08 Feb 2015 23:20:06 +0000

Hallo,

Im Hinweis steht: "Die zugehörigen (nichtdeterministischen) endlichen Automaten bestehen bspw. beide aus nur einem einzigen Zustand,der für $E^\star$ gleichzeitig Endzustand ist und für $\emptyset$ nicht."

Meine Fragen lauten:

1. Der NEA für die leere Menge $\emptyset$ müsste doch aus zwei Zuständen bestehen:

$q_0$ als Startzustand;

$q_1$ als Endzustand (da mindestens ein Endzustand existieren muss) ;

keine Übergänge (da der akzeptierende Automat nie erreicht wird -> leere Sprache) Sind DEA und NEA für $\emptyset$ identisch ?

2. Unterscheiden sich DEA/NEA für die leere Sprache $\emptyset$ und das leere Wort $\lambda$? Beim NEA für $\lambda$ müsste es doch zwei Zustände (einen Startzustand, einen Endzustand und einen $\lambda$-Übergang) geben? DEA für $\lambda$ müsste doch nur einen Zustand (Startzustand und Endzustand in einem; $\lambda$-Übergang in sich) besitzen?

3. DEA/NEA für $E^\star$ besteht doch einfach nur aus einem Zustand (Start- und Endzustand)

Vielen Dank im Voraus!

Wieso kann eine Teilmenge, die nicht regulär ist, Teil einer regulären Sprache sein?

Tue, 13 Jan 2015 22:23:35 +0000

Ich dachte, wenn die "Obersprache" (von der Menge her) regulär ist, ist dies auch die Untersprache. Wir reden hier ja über Mengen und bei Sprachen allgemein gilt doch:

Grammatiken eines Typs i können nur von Sprachen eines Typs j mit j >= i erzeugt werden. Dann müsste ja meiner Überlegung nach eine reguläre Sprache nur reguläre Sprachen enthalten dürfen richtig?

Ach und zur obigen Frage die Antwort: rechtslineare Sprachen sind reguläre Sprachen (dies ist äquivalent)

Wieso ist E* regulär?

Sun, 16 Nov 2014 16:24:20 +0000

E* bedeutet doch alle möglichen Kombinationen aus dem Alphabet E. wie kann das regulär sein? wenn z.B. E ={a,b,c} ist in E* doch auch die a^n b^n c^n enthalten was nicht regulär ist, oder was mache ich falsch?

E* regulär oder nicht?

Sun, 16 Nov 2014 16:22:34 +0000

Die erklärungen von teil 1 und teil2 verwirren mich ein wenig: wenn ich das richtig verstehe wird in der Erklärung von Teil 1 angenommen dass E* regulär ist, bei der zweiten Teilfrage wird angenommen dass E* nicht regulär ist. Welches rifft denn nun zu?