0 Daumen
70 Aufrufe

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

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

von

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community