Ist diese Sprache kontextfrei? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:38 Do 24.06.2004 | | Autor: | hmeier |
Hallo, ich habe irgendwie so das "Gefühl", dass die Sprache nicht kontextfrei ist. Aber hat jemand eine Idee, wie ich das beweisen könnte?
L = {a,b}* - {ww | w {a,b}* }
Mit Hilfe des Pumping Lemmas kann ich zeigen, dass der zweite Teil
M={ww | w {a,b}* }
nicht kontextfrei ist, aber wie für diese gesamte Sprache?
Hat jemand eine Idee?
Danke, Herbert
![[]](/images/popup.gif) http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=22254
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:29 Fr 25.06.2004 | | Autor: | felixs |
> Hallo, ich habe irgendwie so das "Gefühl", dass die Sprache nicht kontextfrei ist.
> Aber hat jemand eine Idee, wie ich das beweisen könnte?
> L = {a,b}* - {ww | w {a,b}* }
> Mit Hilfe des Pumping Lemmas kann ich zeigen, dass der zweite Teil
> M={ww | w {a,b}* }
> nicht kontextfrei ist, aber wie für diese gesamte Sprache?
> Hat jemand eine Idee?
ich hab da sone idee, vielleicht eine beweisskizze ...
also angenommen du kannst beweisen dass M nicht cf ist, dann gibt es einen LBA (man koennte auch annehmen dass es einer ganzen TM bedarf, macht aber keinen unterschied) der M entscheidet. ein LBA ist deterministisch, ist also nach eingabe eines wortes in einem bestimmten zustand. macht man nun aus allen endzustaenden normale zustaende und umgekehrt (voraussgesezt LBA akzeptiert == LBA endzustand), kann man L entscheiden. da die entscheidung 'dieselbe' ist wie fuer M, braucht man auch sicher diesen einen LBA (etwas einfacheres tuts halt nicht, siehe beweis M !cf) um L zu entscheiden, also ist L auch kontextsensitiv und NICHT cf.
vielleicht hilft das
-- felix
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:49 Fr 25.06.2004 | | Autor: | hmeier |
Hallo, da erst in der Vorlesung in zwei Wochen die TM bzw. LBA "drankommen" und die Übungsaufgaben zu "kontextfrei" sind müsste das vielleicht auch irgendwie anders gehen?
Auf jeden Fall Danke für Deinen Tipp,
H.
|
|
|
| |
|
Hallo Herbert,
Auf deine Fragen konnte dir zwar damals niemand vollständig antworten, allerdings habe ich jetzt ein ähnliches Problem gefunden, das schon einmal diskutiert wurde.
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:37 Di 29.06.2004 | | Autor: | felixs |
ich denke es muesste an sich irgendwie via pumping lemma gehen. ich seh noch nicht wie :(
--felix
PS: alternative waere die existenz und der beweis eines satzen nachdem das komplement einer kontextsensitiven sprache nie kontextfrei sein kann (was anschaulich (und nach meiner automatenbastelei) klar sein sollte).
|
|
|
|
