DEA ggü. Stern abgeschlossen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:00 Fr 15.10.2010 | | Autor: | Tobus |
| Aufgabe | | Zeigen sie, dass die von DEA Sprachen akzeptierte Sprachen gegenüber dem Kleene-Stern abgeschlossen sind |
Hallo,
ich soll also zeigen, dass die von einem DEA akzeptierte Sprachen unter dem Stern abgeschlossen sind.
Leider weiß ich gerade nicht, wie ich das zeigen soll, denn der Stern bedeutet ja [mm] L^{n}=L*L^{n-1}.
[/mm]
Ich könnte ja nur zeigen, dass ein Automat z.B. 0 akzeptiert und dann auch 00, 000 usw.
Aber wie kann ich es ganz allgemein zeigen ?
DANKE
|
|
| |
|
Hallo Tobus,
> Zeigen sie, dass die von DEA Sprachen akzeptierte Sprachen
> gegenüber dem Kleene-Stern abgeschlossen sind
Ich denke, Du kannst dir dazu den entsprechenden Teil des Beweises des Satzes von Kleene ansehen. Im Englischen: "Kleene's Theorem". Führe mal eine Google-Suche durch.
Angenommen wir haben eine reguläre Sprache [mm] $L\!$ [/mm] und einen regulären Ausdruck [mm] $r\!$, [/mm] der [mm] $L\!$ [/mm] beschreibt. Diesem Ausdruck entspricht ein NEA. Dann kann man nach der von Kleene entwickelten Methode daraus einen NEA bauen, der dem Ausdruck [mm] $r^{\*}$ [/mm] entspricht.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:00 So 17.10.2010 | | Autor: | Tobus |
Hallo.
Schonmal vielen Dank für deine Antwort.
Ich habe hier einen möglichen Lösungsansatz, bin aber nicht sicher ob der hier so stimmt.
Falls [mm] \gamma=\alpha [/mm] *, so bilden wir aus dem NFA M für [mm] \alpha [/mm] einen Automaten M' für [mm] \gamme [/mm] wie folgt:
M' entsteht aus M wie folgt: M' hat dieselben Startzustände, sowie dieselben Endzustände. Es erhält jeder Zustandsknoten, der eine (mit a beschriftete) Verbindung zu einem der ursprünglichen Endzustände hat, zusätzlich einen mit a beschrifteten Pfeil zu jedem Startzustand.
Durch diese Rückkopplung gilt, dass [mm] T(M')=T(M)*=L(\alpha [/mm] *)
Wäre das so korrekt ?
DANKE
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Di 19.10.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
