Automatentheorie - kontextfreie Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:12 Mi 23.06.2004 | | Autor: | hmeier |
Kann mir jemand einen Tipp geben, wie ich folgenden Beweis anfangen könnte?
Sei Sigma ein Alphabet. Zeigen Sie, dass die Klasse cf L_Sigma der kontextfreien Sprachen abgeschlossen gegenüber dem Schnitt mit regeulären Sprachen über Sigma ist, d. h. Ist L1 cf L_Sigma und L2 REG_Sigma, dann ist L1 geschnitten mit L2 cf L_Sigma
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:31 Mi 23.06.2004 | | Autor: | felixs |
> Sei Sigma ein Alphabet. Zeigen Sie, dass die Klasse cf L_Sigma der
> kontextfreien Sprachen abgeschlossen gegenüber dem Schnitt mit regeulären
> Sprachen über Sigma ist, d. h. Ist L1 cf L_Sigma und L2 REG_Sigma, dann ist
> L1 geschnitten mit L2 cf L_Sigma.
also $ [mm] L_1 [/mm] $ cf und [mm] $L_2$ [/mm] regulaer. $ [mm] \Rightarrow \exists [/mm] $ PDA $ [mm] P=(Z_p,\Sigma,\Gamma,\delta_p,z_p,\#,E_p): L(M)L_1 \wedge \exists [/mm] $ DFA $ [mm] D=(Z_d,\Sigma,\delta_d,z_d,E_d) :L(D)=L_2 [/mm] $
jetzt baut man einen neuen PDA $ [mm] N=(Z_p \times Z_d, \Sigma,\Gamma,\delta_n,(z_p,z_d),\#,E_p \times E_d) [/mm] $ mit $ [mm] \delta_n((x,y),a,A) \ni ((x',y'),B_1 \ldots B_i) \Leftrightarrow \left ( d_p(x,a,A) \ni (x',B_1 \ldots B_i) \wedge \delta_d(y,a)=y') $
zu deutsch:
der neue automat hat jetzt als zustandsmenge das kartesische produkt der zustandsmengen der beiden automaten (das koennen sehr viele sein ;). der spielt jetzt _beide_ automaten _gleichzeitig_ durch und landet nur im endzustand wenn das die beiden andern auch tun wuerden. ich denke das prinzip ist sicher vom schneiden zweier DFAs bekannt (laesst sich da auch leichter einsehen).
um jetzt zu beweisen dass die sprache auch *wirklich* die gewuenschte ist, bedient man sich auch am besten der argumentation: P und D akzeptieren => N auch, weil es eine transitionskette gibt die zu einem endzustand fuehrt.
falls einer von beiden nicht akzeptiert => N auch nicht, weil kein endzustand in sicht ist (remember: endzustand ist ein 2-tupel, alte transitionen von P haben nur einfluss auf koordinate 1, die von D nur auf 2).
viel formaler krieg ich das nicht hin
viel spass trotzdem
-- felix
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:32 Do 24.06.2004 | | Autor: | hmeier |
Hallo, vielen Dank, das leuchtet ein :)
Nur eins verstehe ich im Beweis nicht ganz: "weil es eine transitionskette gibt die zu einem endzustand fuehrt"?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:52 Do 24.06.2004 | | Autor: | hmeier |
ach ja jetzt ist es mir schon klar, Danke nochmals
|
|
|
|
