NEA (Produktautomat) < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Zeigen Sie mit Hilfe der Produktautomatenkonstruktion, daß für je zwei Sprachen, die von NEA's erkannt werden, auch ihre Vereinigung von einem NEA erkannt wird. |
Hallo liebes Forum,
Dieses ist meine erste Informatik-Frage hier, und ich hoffe, jemand Kluges kann sie beantworten 
In einem Skript fand ich o.g. Aufgabe. Meine Lösungsidee ist folgende:
Vorbemerkung:
Für eine Menge $L$ und [mm] $M,N\subseteq [/mm] L$ gilt:
(*) [mm] $(L\setminus M)\cup(L\setminus [/mm] N) = [mm] L\setminus\{M\cap N\}$ [/mm] (nach de Morgan)
Seien [mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] Sprachen über einem Zeichenvorrat [mm] $\Sigma$, [/mm] die von NEA's erkannt werden.
Es gilt:
[mm] $\Sigma^\*\setminus(\Sigma^\*\setminus L_1) [/mm] = [mm] L_1$
[/mm]
und
[mm] $\Sigma^\*\setminus(\Sigma^\*\setminus L_2) [/mm] = [mm] L_2$.
[/mm]
Also folgt mit (*):
[mm] $L_1 \cup L_2 [/mm] = [mm] (\Sigma^\*\setminus(\Sigma^\*\setminus L_1)) \cup (\Sigma^\*\setminus(\Sigma^\*\setminus L_2)) [/mm] = [mm] \Sigma^\*\setminus((\Sigma^\*\setminus(\Sigma^\*\setminus L_1)) \cap (\Sigma^\*\setminus(\Sigma^\*\setminus L_2)))$.
[/mm]
Das [mm] "$\cap$" [/mm] in obiger Zeile lässt sich durch einen Produktautomaten erreichen.
Mein Problem ist aber nun der Nachweis, daß für eine Sprache $L$ jeweils auch [mm] $\Sigma\setminus [/mm] L$ durch einen NEA erkennbar ist.
Für DEA's ist das einfach (Komplementbildung bei Endzuständen), aber für NEA's geht das scheinbar nicht so leicht. An der Stelle im Skript, an der die Aufgabe gestellt wurde, waren DEA's noch nicht definiert; somit "darf" ich auf die Komplementbildung bei DEA's nicht zugreifen (sonst wär's klar, da jeder NEA mittels Potenzmengenkonstruktion in einen DEA umgewandelt werden kann).
Weiß jemand Rat, oder bin ich völlig auf dem Holzweg? Ich weiß nicht, wie ich anders von Durchschnitt auf Vereinigung käme?!
Vielen Dank für einen hilfreichen Tipp im Voraus!!!
|
|
| |
|
Wichtig: Habe mich oben leider vertippt! Unter (*) soll es heißen:
$ [mm] L_1 \cup L_2 [/mm] = [mm] (\Sigma^\*\setminus(\Sigma^\*\setminus L_1)) \cup (\Sigma^\*\setminus(\Sigma^\*\setminus L_2)) [/mm] = [mm] \Sigma^\*\setminus((\Sigma^\*\setminus L_1) \cap (\Sigma^\*\setminus L_2)) [/mm] $.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:24 So 13.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
