Informatiker Board | Druckvorschau: Reguläre Sprache und das Komplement

Geschrieben von bandchef am 21.04.2012 um 15:36:

Reguläre Sprache und das Komplement

Aufgabe
Gegeben sei das Alphabet $[latex] \Sigma = \{0,1\} [/latex]$ und die Sprache $[latex]L_1 = \{ 0,00,000 \} [/latex]$

Geben sie [latex] L_1^c [/latex]

an.

In meinen Folien und Büchern und Internet hab ich leider nirgends eine gute Erklärung gefunden. Sprich ich weiß nicht was damit gemeint ist und auch nicht, wie die Lösung dazu aussieht. Könnt ihr mir weiterhelfen? Das ^c soll ja wohl Komplement bedeuten; also würde die Sprache L_1^c alle Wörter enthalten, die nicht in der Sprache L enthalten sind. Komplement eben. Wie aber sieht das dann hier konkret aus? Wie schreibt man das am besten hin?

So vielleicht: $[latex] L_1^c = \{ 1,11,111 \}[/latex]$

Geschrieben von Karlito am 23.04.2012 um 00:22:

Hi,

konstruiere einen deterministischen endlichen Automaten, welcher die Sprache [latex]L_1[/latex]

erkennt.

Danach tausche Finalzustände gegen nichtfinalzustände und andersrum. Der neue Automat repräsentiert die komplementäre Sprache.

VG,

Karlito