Gegeben ist ein Alphabet Σ = {0, 1}. Wie zeigt man solche Ausdrücke?

Question

Aufgabe Ausdrücke und Sprachen:

Gegeben ist ein Alphabet  Σ = {0, 1} und L1 repräsentiert alle Worte mit ungerader Anzahl von Nullen.

Wie zeigt man solche Ausdrücke?

Answer 1

Es wäre sinnvoll, das Thema von vorne anzuschauen. Inf-schule.de ist ein guter Anlaufpunkt, wenn auch nicht ganz ausführlich.

Für die Sprache L1 über dem Alphabet ∑={0, 1} gibt es keinen reguläreren Ausdruck aus dem einfachen Grund, dass es unendlich viele Wörter gibt, für die die Bedingung gilt.

Die Sprache ist mindestens kontextfrei. Das gilt es jetzt herauszufinden. Versuch eine Produktion für die Sprache zu entwickeln und vereinfache sie soweit wie möglich.

Wenn ich richtig denke, sollte das eine kontextsensitive Sprache (Chomsky Typ 1) sein.

Beste Grüße

Felix

Comments

Ich muss mich korrigieren:

Der Grund ist nicht der, dass es unendlich viele Möglichkeiten gibt, sondern der, dass eine reguläre Sprache nur mit Zuständen zählen kann. Du kannst nicht unendlich viele Wörter mit endlich vielen Zuständen darstellen.