|
|
Sprache erzeugen, regülär, kontextfrei? |
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
|
|
Sprache erzeugen, regülär, kontextfrei? |
|
Hallo Leute!
Es geht um die Grammatik G = ({Z},{a,b,c},{Z::=abcZ, Z::=Epsilon},Z)
Nun soll ich herausfinden, ob L(G) regulär oder kontextfrei ist.
Dafür muss ich ja erst einmal eine Sprache L(G) erzeugen, herleiten oder wie auch immer.
Dass es hier nur (abc)*, kann ich leicht ablesen, daher ist meine Vermutung ja
L(G) = { (abc)^n : n >= 0}
Was habt ihr für Ideen für eine Herleitung dieser Sprache? Dass die Grammatik nur abc beliebig oft erzeugen kann, die Erklärung reicht vielleicht nicht.
Wo wir gerade schon dabei sind. Kann mir vielleicht noch jemand sagen, ob es sich hierbei um eine reguläre oder kontextfreie Sprache handelt? Eins von beidem trifft doch sicherlich zu und ich vermute nach den ersten Überlegungen, dass L(G) kontextfrei ist, aber nicht regulär. Kann mir das jemand bestätigen? Vielleicht seid ihr ja so geübt und könnt das sofort sehen
Grüße
|
|
29.11.2007 07:19 |
|
|
|
RE: Sprache erzeugen, regülär, kontextfrei? |
|
Ich finde Deine Ansätze nicht schlecht.
Ob eine Sprache regulär ist, kann man entweder beweisen, indem man einen Automaten kostruiert, der die Sprache erzeugt (wobei ich nicht weiss, ob Du dessen Sprache dann auch beweisen musst), oder man kann zeigen, dass sie NICHT regulär ist, per Widerspruchsbeweis per PumpingLemma.
In Deinem Fall ist es glaube ich am Einfachsten einen NEA zu konstruieren, das sollest Du ja können. Die erzeugte Sprache dann zu beweisen ist auch nicht SOOO schwer, ist nur bissie Schreibarbeit. Aber warscheinlich brauchst Du das gar nicht.
Kontextfrei heisst doch nur,dass auf der linken Seite der Produktionen nur einzelne Nichtterminale stehen, soweit ich weiss (Das war dann der Punkt, an dem ich das Buch weggelegt habe
). Wenn das stimmt, dann ist ja ziemlich offensichtlich, dass Deine kontextfrei ist.
Wie man aus ner Grammatik ne Sprache herleitet, weiss ich nciht so genau. Aber was DU gemacht hast, ist ja einen regulären Ausdruck zu kontruieren, der die selbe Sprache erzeugt (womit ja die Regularität schon gezeigt wäre).
Aber sonst würd ich sagen, bist Du aufm richtigen Weg.
__________________ I'm 71% Megatron!
|
|
29.11.2007 10:05 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Wenn du eine Sprache durch einen regulären Ausdruck erzeugen kannst, dann ist sie natürlich auch regulär (mach dir den Zusammenhang zwischen DEA, NEA und regulären Ausdrücken klar).
Wenn du eine Grammatik G und eine Sprache L hast und du beweisen willst, dass L = L(G) gilt, wird häufig als Beweismittel vollständige Induktion eingesetzt.
1.) Zeige durch Induktion über die Wortlänge der Wörter . Für den Induktionsanfang zeige . Dann nimm an, zu existiere eine Ableitung (Induktionsvoraussetzung). Jetzt zeige, dass dann auch eine Ableitung existiert.
2.) Zeige durch Induktion über die Ableitungslänge der Ableitungen . Nimm als Voraussetzung an, dass alle Wörter, die mit maximal n Ableitungsschritten erzeugt werden können, in L liegen. Dann mache einen Ableitungsschritt mehr : .
|
|
29.11.2007 11:10 |
|
|
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
|
|
Hallo
Zu dem Zusammenhang mit DEA und NEA und regulären Ausdrücken.
Für
ist regulär und kontextfrei. Jetzt kann ich also einen DEA konstruieren. Aber wenn ich jetzt einen Kellerautomaten angeben soll, ist der DEA dann gleichwertig zum Kellerautomaten?
Regeln der Kellerautomaten haben doch immer so eine Form
Beim DEA reicht allerdings schon
Reicht es, einen DEA zu zeichnen um einen Kellerautomaten anzugeben?
Grüße
|
|
05.12.2007 15:21 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Das ist nur eine Frage des Formalismus. Ignorier den Keller einfach, dann hast du aus dem DEA sofort einen Kellerautomat konstruiert.
|
|
05.12.2007 15:25 |
|
|
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
|
|
Zu dem Kellerautomaten habe ich allgemein noch eine Frage.
Wir haben da das Beispiel
als Kelelrautomaten gezeichnet
Jetzt haben wir im Startzustand zwei Schlingen gehabt, einmal eine mit
1) a, #/A#
und
2) a,A/AA
wobei wir allgemein a,X/y definierten als: Der Kellerautomat liest a, X ist das oberste Zeichen auf dem Stack, schreibe nun y auf den Stack.
Das heißt also
1) lese a, oberstes Element ist # (unterste Stackzeichen), schreibe A#
2) lese a, oberstes Element ist A, schreibe AA
Jetzt mal als Beispiel für aaa, ich verstehe nämlich die Schlingen in Bezug auf den Stack nicht
aaa, der Kellerautmat geht in 1 rein, weil der Stack noch leer ist
dann ersetzt er # durch A#
Zu bearbeiten ist noch aa, er liest ein a, dann geht er in 2), ersetzt das A durch ein AA
Stackinhalt: AA# (wobei links das oberste Element ist)
dann das letzte a wird gelesen. Gehe in 2), ersetze A durch AA und erhalte
A
A
A
#
Ist das so gemeint?
WEnn ich jetzt aber vom Stack löschen möchte, ohne ein b zu lesen, wie kann man das machen? weißt du das zufällig? Das geht vermutlich gar nicht?
Vom Startzustand in einen anderen Zustand, wobei der PFeil beschriftet ist mit
Grüße
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Phoney: 05.12.2007 16:25.
|
|
05.12.2007 16:21 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ich verstehe dein Problem nicht richtig. Die Idee des Kellerautomaten für die Sprache ist folgende:
Für jedes gelesene "a" schiebe ein Symbol auf den Keller. Sobald das erste "b" gelesen wird, gehe in einen neuen Zustand und lösche für jedes "b" ein Symbol vom Keller. Am Ende erhältst du den leeren Keller genau dann, wenn es gleich viele a's wie b's gab. Und ein leerer Keller ist das Akzeptanzkriterium.
Beispielwort: aabb
aabb , #
abb , A#
bb , AA#
b , A#
eps, #
|
|
12.12.2007 13:52 |
|
|
|
|
|
|
|