kontextfreie Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich habe mal eine Verständnisfrage...und zwar ist (laut meinem Skript) die Sprache L(G) = [mm] {a^{m} b^{m} c^{n} | m,n \ge 1} [/mm] kontextfrei.
Jetzt versuche ich mir bei kontextfreien Sprachen immer einen Kellerautomaten vorzustellen der mit beispielsweise einem Zeichen a eine Buchstabenfolge m auf den Keller schreibt und mit einem anderen Zeichen b den Keller über m b´s wieder leert um in den akzeptierenden Zustand übergehen zu können. Mein vorgehen funktioniert allerdings nicht bei obiger Sprache. Warum ist diese Sprache kontextfrei? Ich kann die a´s mit den b´s wieder "gut" machen, aber was wird aus den c´s ? So kann ich den Keller doch niemals leeren oder wie habe ich mir das vorzustellen?
Bin für jede Hilfe dankbar!
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:32 Mi 25.01.2012 | | Autor: | sandp |
> Hallo,
>
> ich habe mal eine Verständnisfrage...und zwar ist (laut
> meinem Skript) die Sprache L(G) = [mm]{a^{m} b^{m} c^{n} | m,n \ge 1}[/mm]
> kontextfrei.
>
> Jetzt versuche ich mir bei kontextfreien Sprachen immer
> einen Kellerautomaten vorzustellen der mit beispielsweise
> einem Zeichen a eine Buchstabenfolge m auf den Keller
> schreibt und mit einem anderen Zeichen b den Keller über m
> b´s wieder leert um in den akzeptierenden Zustand
> übergehen zu können. Mein vorgehen funktioniert
> allerdings nicht bei obiger Sprache. Warum ist diese
> Sprache kontextfrei? Ich kann die a´s mit den b´s wieder
> "gut" machen, aber was wird aus den c´s ? So kann ich den
> Keller doch niemals leeren oder wie habe ich mir das
> vorzustellen?
>
> Bin für jede Hilfe dankbar!
>
> Liebe Grüße
Hey,
ja du musst den Keller ja auch nichtmehr leeren, das wichtige ist dass du genau gleich viele a's wie b's hast und das kannst du ja mit dem Keller.
Wenn dann noch mind. ein c kommt akzeptiert dein Kellerautomat.
Weil dann benutzt du nur noch eine Regel, die ein c liest und es auf den Kellerlegt und in den gleichen Zustand geht, dieser Zustand muss als Endzustand in deinem Tupel definiert sein.
Zur Vollständigkeit:
Es gibt Kellerautomaten die bei leerem Keller akzeptieren und es gibt Kellerautomaten die akzeptieren, sobald sie in einem Endzustand sind.
Erkennen tut man sie, bei der Definition ihrer Tupel.
6-Tupel, wenn der Kellerautomat bei leerem Keller akzeptiert
7-Tupel, wenn der Kelleratumoat akzeptiert, sobald er in einem Endzustand ist (hier brauchst du eine Menge mehr für die Menge der Endzustände)
Gruß sandp
|
|
|
| |
|
Also habe ich am Ende sozusagen einen Endzustand, der beliebig viele, auch unendlich viele, c´s auf den Keller schreibt und irgendwann akzeptiert? Also steht dann da sowas wie
[mm] (f,c,\lambda) \to [/mm] (f,c) wobei f mein Endzustand ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:00 Do 26.01.2012 | | Autor: | sandp |
> Also habe ich am Ende sozusagen einen Endzustand, der
> beliebig viele, auch unendlich viele, c´s auf den Keller
> schreibt und irgendwann akzeptiert? Also steht dann da
> sowas wie
> [mm](f,c,\lambda) \to[/mm] (f,c) wobei f mein Endzustand ist?
ja unendlich viele c's kann es ja bei uns nicht geben, da wir ein festes n haben
aber sonst richtig
|
|
|
| |
|
Ok...aber warum ist dann die Sprache [mm] \{a^{n} b^{n} c^{n} | n \in \IN \} [/mm] nicht kontextfrei? Da könnte man das doch dann genauso machen wie oben beschrieben, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:20 Do 26.01.2012 | | Autor: | sandp |
> Ok...aber warum ist dann die Sprache [mm]\{a^{n} b^{n} c^{n} | n \in \IN \}[/mm]
> nicht kontextfrei? Da könnte man das doch dann genauso
> machen wie oben beschrieben, oder?
ja du musst bei dieser Sprache garantieren, dass die a's b's und c's gleich viele sind. Für die a's und b's ist das ja nicht schwer indem du, wenn du die a's liest immer ein Element auf den Keller packst, wenn du dann die b's liest dann holst du die Elemente vom Keller wieder runter.
Dann ist der Keller leer und du liest die c's, aber wie willst du jetzt garantieren dass es genau so viele sind wie a's und b's ?
Genau daher ist die Sprache nicht kontextfrei.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:17 Do 26.01.2012 | | Autor: | judithlein |
Einleuchtend! Vielen Dank!!!!
|
|
|
|
