0 Daumen
491 Aufrufe

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?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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

Avatar von

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community