Ausdrücke und Sprachen

Question

Guten Abend Leute,

wir schreiben in drei Wcohen eine kleine "Prüfung" in technischer Informatik und ich komme bei den regulären Ausdrücken und Automaten nicht mehr weiter. In der Probeklausur die wir zum lernen bekommen haben steht diese Aufgabe:

gegeben ein Alphabet  Σ = {0, 1} und L1 repräsentiert alle Worte mit ungerade anzahl von Nullen.

ich weiß nicht wie man solche Ausdrücke zeigt in den Folien gibt es leider keine Beispile zumindestens die ich verstehe.

Wäre froh wenn ihr mich aufklären könntet.

MfG

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

danke für die hilfreiche Antwort:)

---

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.