Suffix abgeschlossen unter RS? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:58 Fr 25.07.2014 | | Autor: | PaulW89 |
| Aufgabe | Für $L [mm] \subseteq \Sigma^{\*}$ [/mm] definieren wir
[mm] $\operatorname{suffix}(L) [/mm] := [mm] \{ v \in \Sigma^{\*} \ : \ \text{es gibt ein} \ u \in \Sigma^{\*} \ \text{mit} \ uv \in L \}$
[/mm]
Beweisen Sie, dass die regulären Sprachen unter der suffix-Operation abgeschlossen sind
(Das "E" in [mm] E^{\*} [/mm] soll ein großes Sigma sein, also das Eingabealphabet.) |
Edit schachuzipus: dann schreib es doch  /Sigma
Hallo Leute,
heute habe ich mal eine Frage zu obiger Aufgabe, zu der mir der Ansatz fehlt.
So viel weiß ich: Um zu zeigen, dass eine Operation unter den RS abgeschlossen ist, muss gezeigt werden, dass ein RegEx oder ein DEA existiert, der die Sprache akzeptiert.
Kann ich nun einfach einen DEA konstruieren, der u akzeptiert und dann in einen zweiten DEA springt, der auch v akzeptiert? Reicht das als Beweis?
Die Thematik ist für mich leider neu..
Das gleiche dürfte dann auch für die Präfix-Operation gelten, oder?
Ich freue mich auf Anregungen!
Viele Grüße,
Paul!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:02 Sa 02.08.2014 | | Autor: | PaulW89 |
Scheint euch hier also zu gehen wie mir: Langweilige Materie.
Hat wirklich niemand eine Idee? Ist in der Klausur eigentlich nur ne Kurzfrage.
Viele Grüße,
Paul!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:33 Sa 16.08.2014 | | Autor: | felixf |
Moin!
> Für [mm]L \subseteq \Sigma^{\*}[/mm] definieren wir
>
> [mm]\operatorname{suffix}(L) := \{ v \in \Sigma^{\*} \ : \ \text{es gibt ein} \ u \in \Sigma^{\*} \ \text{mit} \ uv \in L \}[/mm]
>
> Beweisen Sie, dass die regulären Sprachen unter der
> suffix-Operation abgeschlossen sind
>
> (Das "E" in [mm]E^{\*}[/mm] soll ein großes Sigma sein, also das
> Eingabealphabet.)
>
>
> Edit schachuzipus: dann schreib es doch
> /Sigma
>
> Hallo Leute,
>
> heute habe ich mal eine Frage zu obiger Aufgabe, zu der mir
> der Ansatz fehlt.
> So viel weiß ich: Um zu zeigen, dass eine Operation unter
> den RS abgeschlossen ist, muss gezeigt werden, dass ein
> RegEx oder ein DEA existiert, der die Sprache akzeptiert.
>
> Kann ich nun einfach einen DEA konstruieren, der u
> akzeptiert und dann in einen zweiten DEA springt, der auch
> v akzeptiert? Reicht das als Beweis?
> Die Thematik ist für mich leider neu..
Ueber endliche Automaten zu gehen ist eine gute Idee. Mach am besten einen Nicht-Deterministischen, das ist wesentlich einfacher und du weisst ja (aus der Theorie), dass es dann auch einen entsprechenden deterministischen Automaten gibt.
Fuege einen neuen Zustand $S'$ hinzu, der Startzustand wird. Wenn $A [mm] \overset{b}{\to} [/mm] C$ im alten Automat ein Uebergang ist (von Zustand $A$ nach $C$, wenn Eingabe $b$ da ist), der (wichtig!) vom alten Startzustand aus erreicht werden kann, dann definierst du im neuen Automaten zusaetzlich den Uebergang $S' [mm] \overset{b}{\to} [/mm] C$.
Wenn der alte Automat eine Eingabekette [mm] $b_1, \dots, b_n$ [/mm] akzeptiert (und somit das Wort [mm] $b_1 \dots b_n$), [/mm] dann akzeptiert der neue Automat alle Suffixe davon, also z.B. [mm] $b_i, \dots, b_n$.
[/mm]
Und akzeptiert der neue Automat umgekehrt eine Eingabe, so kannst du diese zu einer Eingabe erweitern, die auch der alte Automat akzeptiert, indem du etwas davorhaengst (dazu ist das oben mit "wichtig!" wichtig -- ansonsten geht das nicht umbedingt).
> Das gleiche dürfte dann auch für die Präfix-Operation
> gelten, oder?
Ja. Der Beweis dafuer ist allerdings einfacher: nimm einen endlichen Automaten und markier zusaetzlich alle Zustaende als Endzustaende, von denen man einen Endzustand erreichen kann.
LG Felix
|
|
|
|
