Sprache aller Präfixe der Wörter aus L?
Könnte mir jemand die folgende Aufgabe erklären?
Vielen Dank!
Welche Eigenschaften muss für L gelten damit sie b und c erfüllt? verstehe nix
1 Antwort
Du betrachtest jeweils eine Sprache L über einem Alphabet A sowie die Präfixsprache p(L), die alle Wörter enthält, die Präfix eines Wortes aus L sind.
In der ersten Aufgabe ist eine Sprache gesucht, bei der alle Wörter über A in der Präfixsprache liegen, es aber unendlich viele Wörter gibt, die nicht in L liegen.
Die Sprache aller Wörter gerader Länge ist ein Beispiel. Es gibt unendlich viele Wörter, die nicht in dieser Sprache liegen (alle ungerader Länge). Gleichzeitig kannst du von jedem Wort den letzten Buchstaben entfernen und bekommst so alle Wörter ungerader Länge, d. h. die Präfixsprache umfasst alle Wörter über A.
Die Sprache der Palindrome ist ein anderes Beispiel. Es gibt unendlich viele Wörter, die keine Palindrome sind und du bekommst alle Wörter, wenn du jedes Palindrom halbierst.
In der zweiten Aufgabe ist eine Sprache gesucht, für die es unendlich viele Wörter über A gibt, die Präfix eines Wortes aus L sind, und auch unendlich viele, die es nicht sind.
{a}* ist für das Alphabet {a, b} ein Beispiel, denn {a}* sind alle Präfixe dieser Sprache und {b}+ sind bereits unendlich viele Wörter, die kein Präfix sind.
a^nb^n ist ebenfalls ein Beispiel, denn {a}* sind bereits unendlich viele Präfixe und {b}+ sind z. B. unendlich viele Wörter, die kein Präfix sind.
