kontextfreie Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich dachte bis gerade ich könne erkennen, wann eine Sprache kontextfrei ist und wann nicht. Aber jetzt habe ich ein Beispiel gefunden, das mich wieder etwas durcheinander bringt:
Die Sprache L= { [mm] a^n b^n a^n b^n [/mm] | n [mm] \ge [/mm] 1 } ist nicht kontextfrei.
So, meine offensichtliche Frage, warum ist diese Sprache nicht kontextfrei? Man könnte doch ohne Probleme einen Kellerautomaten angeben der die ersten a´s auf den Keller schreibt, mit den ersten b´s wieder löscht und dann wieder a´s auf den Keller schreibt, die er mit den b´s dann wieder löschen kann --> Kellerautomat akzeptiert mit leerer Eingabe und leerem Keller also waren die Anzahl der a´s und b´s immer gleich gewesen.
Ich kapier das gerade wirklich nicht. Danke schon mal!
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:54 Mo 20.02.2012 | | Autor: | sandp |
hey,
ok jetzt hast du einen Kellerautomaten angegeben, aber ist dieser korrekt?
Wie sieht es mit dieser Sprache aus?
Sprache L= { [mm] a^n b^n a^{n+1} b^{n+1} [/mm] | n [mm] \ge [/mm] 1 }
Würde dein Kellerautomat auch diese Sprache akzeptieren?
Was ist also der Grund, dass deine Sprache nicht kontextfrei ist?
Gruß sandp
|
|
|
| |
|
Sie ist nicht kontextfrei, da ich mir nicht speichern kann wie viele a´s und b´s ich am Anfang hatte. Ist mir heute Morgen nach kurzem Überlegen dann auch klar gewesen. Es wäre aber die Sprache L= { [mm] a^{n} b^{n} a^{m} b^{m} [/mm] | n [mm] \not= [/mm] m } kontextfrei. Hier muss der Kellerautomat nämlich garnicht mehr wissen wieviele a´s und b´s er am Anfang hatte und kann unabhängig davon dann m a´s lesen und auf den Keller schreiben und den Keller dann wieder mit m b´s leeren.
Aber jetzt habe ich mal noch eine ganz allgemeine andere Frage:
Es geht um deterministische und nichtdeterministische Kellerautomaten. Die deterministischen akzeptieren ja nur über einen definierten Endzustand. Das bedeutet der Keller oder die Eingabe müsste auch noch nicht aufgebraucht sein um in einen akzeptierenden Zustand zu gelangen. Als Beispiel ist ja die Sprache L= { [mm] a^{m} b^{n} [/mm] | n>m } deterministisch kontextfrei.
Die nichtdeterministischen kontextfreien Kellerautomaten akzeptieren im Allgemeinen über den leeren Keller, d.h. wenn Keller und Eingabe leer sind, geht der Kellerautomat in einen akzeptierenden Zustand.
Die Sprache L= { [mm] a^{n} b^{n} [/mm] | n [mm] \ge [/mm] 1 } ist sowohl deterministisch kontextfrei als auch nichtdeterministisch ktf. Typische nichtdeterministische kontextfreie Sprachen sind eben Sprachen bei denen der Automat dazu "gezwungen" ist zu raten. Beispielsweise bei der Sprache L = { ww' | w [mm] \in [/mm] { a,b } , w' = gespiegeltes Wort zu w }. Hier müsste der Automat nämlich irgendwann raten, wann das Wort w am Ende ist und das Wort w' beginnt.
Ist das alles was man dazu wissen muss? Hab bald Prüfung, deswegen...
DANKE!
> Gruß sandp
>
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:16 Di 21.02.2012 | | Autor: | sandp |
> Sie ist nicht kontextfrei, da ich mir nicht speichern kann
> wie viele a´s und b´s ich am Anfang hatte. Ist mir heute
> Morgen nach kurzem Überlegen dann auch klar gewesen. Es
> wäre aber die Sprache L= { [mm] a^{n} b^{n} a^{m} b^{m} [/mm] | n
> [mm] \not= [/mm] m } kontextfrei. Hier muss der Kellerautomat nämlich
> garnicht mehr wissen wieviele a´s und b´s er am Anfang
> hatte und kann unabhängig davon dann m a´s lesen und auf
> den Keller schreiben und den Keller dann wieder mit m b´s
> leeren.
stimmt leider auch nicht ganz, da du nicht kontrollieren kannst ob m [mm] \not= [/mm] n ist
>
> Aber jetzt habe ich mal noch eine ganz allgemeine andere
> Frage:
> Es geht um deterministische und nichtdeterministische
> Kellerautomaten. Die deterministischen akzeptieren ja nur
> über einen definierten Endzustand. Das bedeutet der Keller
> oder die Eingabe müsste auch noch nicht aufgebraucht sein
> um in einen akzeptierenden Zustand zu gelangen. Als
> Beispiel ist ja die Sprache L= { [mm] a^{m} b^{n} [/mm] | n>m }
> deterministisch kontextfrei.
> Die nichtdeterministischen kontextfreien Kellerautomaten
> akzeptieren im Allgemeinen über den leeren Keller, d.h.
> wenn Keller und Eingabe leer sind, geht der Kellerautomat
> in einen akzeptierenden Zustand.
> Die Sprache L= { [mm] a^{n} b^{n} [/mm] | n [mm] \ge [/mm] 1 } ist sowohl
> deterministisch kontextfrei als auch nichtdeterministisch
> ktf. Typische nichtdeterministische kontextfreie Sprachen
> sind eben Sprachen bei denen der Automat dazu "gezwungen"
> ist zu raten. Beispielsweise bei der Sprache L = { ww' | w
> [mm] \in [/mm] { a,b } , w' = gespiegeltes Wort zu w }. Hier müsste
> der Automat nämlich irgendwann raten, wann das Wort w am
> Ende ist und das Wort w' beginnt.
> Ist das alles was man dazu wissen muss? Hab bald Prüfung,
> deswegen...
>
klingt schonmal gut, ich würde noch die formale Definitionen lernen(falls du das noch nicht gemacht hast) weil bei der Definition der Kellerautomaten mit Hilfe der Tupel wird auch sofort klar ob er auf leerem Keller akzeptiert oder ob er akzeptiert wenn er in einem Endzustand ist.
Akzeptiert auf leerem Keller : 6-Tupel
Akzeptiert in einer Menge von Endzustände: 7-Tupel
ach und jeder deterministische Kellerautomat ist auch gleichzeitig ein nichtdeterministischer Kellerautomat
Viel Erfolg bei deiner Prüfung
> DANKE!
> > Gruß sandp
> >
> >
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:25 Di 21.02.2012 | | Autor: | judithlein |
Alles klar :) Vielen Dank!
|
|
|
|
