Sprache erzeugen, regülär, kontextfrei?

Neue Frage »

Auf diesen Beitrag antworten »
Phoney 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
Augenzwinkern

Grüße
 
Auf diesen Beitrag antworten »
JROppenheimer 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 smile ). 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.
Auf diesen Beitrag antworten »
Tobias

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 [latex]L \subseteq L(G)[/latex] durch Induktion über die Wortlänge der Wörter [latex]w \in L[/latex]. Für den Induktionsanfang zeige [latex](abc)^0 = \varepsilon \in L(G)[/latex]. Dann nimm an, zu [latex](abc)^n[/latex] existiere eine Ableitung [latex]Z \Rightarrow^\ast (abc)^n[/latex] (Induktionsvoraussetzung). Jetzt zeige, dass dann auch eine Ableitung [latex]Z \Rightarrow^\ast (abc)^{n+1}[/latex] existiert.

2.) Zeige [latex]L(G) \subseteq L[/latex] durch Induktion über die Ableitungslänge der Ableitungen [latex]Z \Rightarrow^\ast w[/latex]. 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 : [latex]Z \Rightarrow abcZ \Rightarrow^{\leq n} abc w[/latex].
Auf diesen Beitrag antworten »
Phoney

Hallo
Zu dem Zusammenhang mit DEA und NEA und regulären Ausdrücken.
Für
[latex]G = (\{Z\},\{a,b,c\},\{Z::=abcZ, Z::=\varepsilon\},Z) [/latex]

[latex]L(G) = \{ (abc)^n : n \ge 0\} [/latex]

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
[latex]\delta (q_c,\varepsilon,Z_0) -> (q_j, \epsilon) [/latex]

Beim DEA reicht allerdings schon
[latex]\delta(q_0,a) = q_1[/latex]
Reicht es, einen DEA zu zeichnen um einen Kellerautomaten anzugeben?

Grüße
 
Auf diesen Beitrag antworten »
Tobias

Das ist nur eine Frage des Formalismus. Ignorier den Keller einfach, dann hast du aus dem DEA sofort einen Kellerautomat konstruiert.
Auf diesen Beitrag antworten »
Phoney

Zu dem Kellerautomaten habe ich allgemein noch eine Frage.
Wir haben da das Beispiel [latex] L=\{a^nb^n | n \in \mathbb{N}\} [/latex]
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 [latex]\varepsilon, A/ \varepsilon[/latex]

Grüße Wink
Auf diesen Beitrag antworten »
Tobias

Ich verstehe dein Problem nicht richtig. Die Idee des Kellerautomaten für die Sprache [latex] L=\{a^nb^n | n \in \mathbb{N}\} [/latex] 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, #
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »