Zeigen: Sprache kontextfrei < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich habe ein Problem mit folgender Aufgabe:
Angenommen L1 und L2 seien reguläre Sprachen.
Zeigen Sie, dass dann die Sprache
[mm] L:= \{ xy | x \in L_{1}, y \in L_{2} [/mm] und [mm] |x| = |y| \}[/mm]
kontextfrei ist.
Im zweiten Teil der Aufgabe, soll man zeigen, dass die in Teil 1 konstruierte Sprache L nicht notwendigerweise regulär ist.
----
Ich habe dort bisher noch keine Idee wie ich anfangen soll.
Ich könnte mir bei Aufgabenteil a denken, dass man über die Abgeschlossenheit kontextfreier Sprachen unter Verkettung geht.
Aber ich habe noch keine Idee inwiefern.
Habt ihr ein paar Tipps für mich, danke schonmal
LG
matze
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Mi 11.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
