Informatiker Board | Theoretische Informatik | Sprache erzeugen, regülär, kontextfrei?

Informatiker Board » Themengebiete » Theoretische Informatik » Sprache erzeugen, regülär, kontextfrei?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Sprache erzeugen, regülär, kontextfrei?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Sprache erzeugen, regülär, kontextfrei?

Zitatantwort auf diesen Beitrag erstellen

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

29.11.2007 07:19

Nehmen Sie Phoney in Ihre Freundesliste auf

JROppenheimer
Foren As

Dabei seit: 17.11.2007
Beiträge: 94

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.

__________________
I'm 71% Megatron!

29.11.2007 10:05

Nehmen Sie JROppenheimer in Ihre Freundesliste auf

MSN Passport-Profil von JROppenheimer anzeigen

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 $[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]$ .

29.11.2007 11:10

Nehmen Sie Tobias in Ihre Freundesliste auf

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
$[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

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 $[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

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 $[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, #

12.12.2007 13:52

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Sprache erzeugen, regülär, kontextfrei?