| Zeige Beiträge 1 bis 13 von 13 Treffern |
|
 Thema: Wann ist eine Grammatik kontextfrei? |
|
|
hmm..
OK, kannst du dann bitte je ein Beispiel zu einer reguläre und kontextfreien Grammatik nennen, so dass ich den Unterschiede sehe?
Danke und Grüße
Daniel
|
|
| Thema: Wann ist eine Grammatik kontextfrei? |
|
|
Ja dann sehe ich denn Unterschied zu einer CfG darin, dass man in der Lage ist folgendes zu machen: S-aABc also noch die Option noch ein Nichtterminal einzufügen.
|
|
| Thema: Wann ist eine Grammatik kontextfrei? |
|
|
mir geht es mehr um die form.
Wollte den Unterschied von regulären und kontextfreien Produktionen verstehen.
Da es ja eine reguläre Grammatik sein sollte müsste dann die Produktion wie folgt nicht erlaubt sein: 1. S-> aAB
2. S->aAc ?
Fragen:
A: Ist die reguläre Grammatik wie bei 1 richtig? also mehrere Nichtterminale nach a ?
B: Die 2. Grammatik müsste allerdings eine CfG sein oder?
Danke und Grüße
Daniel
|
|
| Thema: Wann ist eine Grammatik kontextfrei? |
|
|
Also ich habe das letzte auf eine reguläre Sprache/Grammatik bezogen.
abc ist eine Wort das von einer regulären Grammatik erzeugt werden soll.
Alternativ hatte ich gedacht soll auch nur a| abc erzeugt werden können.
Also sowohl "a" als auch "abc" soll meine reguläre Grammatik erzeugen.
Gruß
Daniel
|
|
| Thema: Wann ist eine Grammatik kontextfrei? |
|
|
also nur die Möglichkeit und Art der Produktionsregeln?
Bei einer CfG können Produktionen der Art: S-> aBCa |aBC|Abc|AbC
und bei regulären Sprachen können nur Produktionen der Art: S-> aA|epsilon oder S->Aa|epsilon.
Wie werden enstehen wörter bei regulären Grammatiken?
Kannst du mir vielleicht ein kleines Beispiel geben?
Wie lautet die Grammatik zu abc?
So zB.:?
S->aB
B->bc |epsilon
??
Vielen Dank und Grüße
Daniel
|
|
| Thema: Wann ist eine Grammatik kontextfrei? |
|
|
Hallo,
ich habe letztens eine einfache Frage gesehen die ich nicht kurz und knapp beantworten konnte.
Wann ist eine Grammatik kontextfrei?
Kann die Frage kurz und knapp beantwortet werden? Wäre super.
Danke und Grüße
Daniel
|
|
| Thema: Kellerautomat |
|
|
Ok, mir ging es auch nicht um die KOnstruktion des Automaten sondern um das Verständnis. Automaten kommen doch nur in der Theorie vor.
Da ich im yacc eine CFG angebe und es dazu einen aquivalenten Nichtdeterm. Kellerautomaten gib, gehe ich davon aus, dass der Parser der eine CFG erhält eben so arbeitet.
Also z.B. genauso viele a`s wie b`s oder Klammer auf wie zu!
Danke dir vielmals Tobias.
Schöne Grüße
Daniel
|
|
| Thema: Kellerautomat |
|
|
Also zu jeder cfg gibt es einen Nichtdeterministischen Kellerautomaten. Wenn ich eine CFG der Form:
S-> AB
A-aabB
B usw....
habe ist auch gleichzeigt mein Kellerautomat konstruiert, da es die Wörter die durch die CFG gebildet werden können verarbeiten kann. So richtig?
Wenn ich in der Form: L={a^nb^n|nelement N} eine CFSprache beschreibe, existiert auch ein Kellerautomat der diese Wörter abarbeiten kann?
Danke
Daniel
|
|
| Thema: Kellerautomat |
|
|
Danke dir für die Links!
Ich konstruiere also keinen expliziten Kellerautomaten. Dieser wird über eine CFG festgelegt oder eine Sprache gemäß L={a^nb^n|neN} erzeugt.
Hab ich es richtig verstanden?
Ich lese es mir noch durch :-)
Gruß
Daniel
|
|
| Thema: Kellerautomat |
|
|
| Zitat: |
Original von Tobias
| Zitat: |
| Wenn eine öffnende Klammer kommt, weiss der Automat dass auch eine schließende Klammer kommen muss zur syntaktischen Korrektheit. |
Der Automat weiß garnichts. Je nachdem, wie der Automat festgelegt wurde, kann man mit ihm eine Sprache erkennen, die gleichviele offene wie geschlossene Klammern enthält.
|
Wie legt man sie fest? Könntest du mir Bitte ein Beispiel nennen.
| Zitat: |
Original von Tobias
[QUOTE]Woher weiss der Kellerautomat das? Das kann es ja nur wissen, wenn alle Zeichen ebenfalls in den Keller wandern. |
Nein. Eine einfache Strategie ist, nur offene Klammern auf den Keller zu schreiben und bei jeder geschlossenen Klammer ein Symbol wieder vom keller zu löschen. Ist der Keller am Ende leer, dann wird das Wort erkannt.
| Zitat: |
Original von Tobias
Du musst dir klar machen, dass kontextfreie Grammatiken und nichtdeterministische Kellerautomaten dieselbe Sprachklasse (kontextfreie Sprachen) beschrreiben können. Deshalb gibt es für jede CFG einen Kellerautomat und andersrum, die dieselbe Sprache entscheidet. Wenn du zu deiner CFG einen äquivalenten nichtdet. Kellerautomaten baust und deine Grammatik die richtige Klammerung beachtet, dann tut dies natürlich dein Automat auch. |
Genau, das fehlt mir. Bitte ein Beispiel nennen.
Meinst du eine Grammatik a la:
S-AB
A-aabB
B->(B)|epsilon
Wäre das z.B. so eine Grammatik und dann eine entsprechenden nichtdet. Kellerautomaten?
Kannst du mir vielleicht zu meiner CFG oder zu einer beliebigen von dir aus ein Kellerautomaten als Beispiel nennen. Das würde mir helfen, die Thematik besser zu verstehen. Da liegen meine Probleme.
Danke
Daniel
|
|
| Thema: Kellerautomat |
|
|
Guten Tag Informatikerboard,
ich verstehe leider die Funktionsweise eines Kellerautomaten nicht genau.
Kontextfreie Grammatiken bzw. Sprachen werden als Kellerautomaten dargestellt.
Ich habe das so verstanden, dass bei jeder Eingabe eines Zeichens dieser auch in den Keller geschrieben wird. ?!
Wenn eine öffnende Klammer kommt, weiss der Automat dass auch eine schließende Klammer kommen muss zur syntaktischen Korrektheit.
Woher weiss der Kellerautomat das? Das kann es ja nur wissen, wenn alle Zeichen ebenfalls in den Keller wandern.
Woher weiss der Automat, dass bei "(" ebenfalls ein ")" kommen muss? Bei einem "a" aber nicht.
Hängt das mit meiner Grammatik zusammen? Also wenn ich z.B. diese Grammatik festlege:
S->AB
A->(B)
B->aba|epsilon?
Ich hoffe ihr könnt mir helfen.
VLG
Daniel
|
|
|
| Zeige Beiträge 1 bis 13 von 13 Treffern |
|
|
|
