abschluss kontextfreie sprache < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:49 Di 09.01.2007 | | Autor: | AriR |
hey leute
verstehe leider nicht so genau, warum der durschnitt von zwei kontextfreien sprachen [mm] L_1 [/mm] und [mm] L_2 [/mm] nicht wieder eine kontextfreie sprache ergibt [mm] L_3.
[/mm]
man schränkt doch sozusagen die Regelen der Grammatik von [mm] L_1 [/mm] auf die regeln ein, die auch in [mm] L_2 [/mm] enthalten sind und erhält [mm] L_3 [/mm] und die befehle haben dann doch alle noch die form die kontextfreie Grammatik verlangt oder nicht?
wäre nett, wenn mir da jemand weiterhelfen könnte
Gruß Ari
|
|
| |
|
Hallo Ari,
kennst Du das Gegenbeispiel
[mm] L_1=\{a^nb^nc^m|n,m\in\IN\},\:\: L_2=\{a^nb^mc^m|n,m\in\IN\} [/mm] ?
[mm] L_1\cap L_2 [/mm] ist nicht kontextfrei, zB wg. Pumping-Lemma.
Und es ist halt nicht so, daß man die Durchschnittbildung einfach über die Grammatiken direkt bewerkstelligen kann.
Mach Dir das mal einfach klar anhand der Definition von Grammatiken und den von ihnen erzeugten Sprachen.
Gruß,
Mathias
|
|
|
|
