Beweis das eine Sprache reg. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:56 Mi 11.04.2012 | | Autor: | Parkan |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Sei $L\subseteq\Sigma^{\star}$ eine beliebige Sprache und $a\in\Sigma$. Definiere:
$La := \{w\in \Sigma^{\star} \mid \ \text{es gibt ein Wort 'wa' in } L\}$
$La$ entsteht also aus $L$, wenn man nur auf $a$ endende Worte aus $L$ betrachtet und bei denen dieses letzte $a$ streicht.
Zeige: Wenn $L \subseteq \Sigma$ eine beliebige reguläre Sprache ist, dann ist auch La regulär. |
Ich habe versucht einen DFA zu zeichnen der La akzeptiert, aber egal wie ich das mache ist dieser DFA mächtiger als nötig. Mir fehlt also der Ansatz wie ich das beweisen kann. Kann mir da ein Tipp geben?
Mein DFA sieht so aus.
x={a..z)
y= x ohne a
Z1,Z2 sind Zustände, wobei Z2 ein Endzustand ist
Z1---x-->Z1
Z1---y-->Z2
Also endet kein Wort mit einem a
Danke
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Fr 13.04.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
