Brauche Hilfe bei der BNF (Backus-Naur Form)

Blue-Tiger

Moin! Ich hab da ein kleines Problem mit einer Aufgabe, die uns von unserm Professor aufs Auge gedrueckt wurde... leider ohne uns ueberhaupt eine gute (oder auch nur zusammenhaengende) Beschreibung der Backus-Naur Form zu geben...
Im Netz find ich leider keine ausreichend detailierte Beschreibung der BNF (nach 1-2 Seiten gehts immer ueber in Parsing-Regeln und Compilerbau). Vom Buch, das uns als Skriptum empfohlen wurde, haben uns Hoehersemestrige abgeraten, also sitz ich vorerst mal mit recht mageren Infos um die BNF zu Hause rum... wer also Tutorials oder eBooks oder sonstige Hinweise kennt, dem waer ich dankbar!

Zum eigentlichen Problem:
Die Aufgabe lautet, eine formale Sprache zu definieren, aus allen Worten besteht, die gleich viele 'a' und 'b' enthalten.
Mein Problem sind die "gleich viele" a und b pro Wort.

In RegEx, wie es sie z. B. in Perl gibt, kann ich Ober- und Untergrenzen fuer Wiederholungen eines Ausdrucks angeben, da laut unserm Prof. die BNF irgendwas mit RegEx zu tun hat (so genau konnt ich das aus der Vorlesung nicht rausfiltern), dacht ich mir, damit eine Loesung der Aufgabe zu basteln. Leider hab ich bisher nix gefunden, womit ich solche Ober- und Untergrenzen angeben kann. Bin deshalb etwas ratlos und fuer Hilfe dankbar

Mein Loesung sieht also momentan so aus, dass ich es nicht erlaube, ein Zeichen 2x hintereinander angebe:

C = {a, b, ' '}, S Teilmente von C* definiert durch
<SPRACHE> ::= <WORT> [<LEERZEICHNEN><WORT>]
<WORT> ::= {ab | ba }+
<LEERZEICHEN ::= ' '

(Wer sonstige Fehler in der Definition sieht darf sich gern melden!).

Das Problem daran: "aabb" waere laut Aufgabenstellung ein gueltiges Wort, laut meiner Syntax aber leider nicht.

Hi,

<WORT> ::= {a<WORT>b}+

geht.

Jockel

Blue-Tiger

THX a lot

kennst du zufaellig auch irgenwelche Online-Quellen, wo man sich ueber die BNF bzw. die EBNF schlauer machen kann?

Ponto

Jockelx schrieb:

Hi,
<WORT> ::= {a<WORT>b}+
geht.

Jockel

Und wie macht man damit ein ba?

Na gut,

Wort muss natürlich auch nach epsilon gehen.

Ach, sorry deine Frage falsch gelesen.

Ich glaube aber, dass a vor b stehen muss, sonst gibt's halt
Zusatzregel:

<WORT> ::= {a<WORT>b}+ | {b<WORT>a}+

Ponto

Jockelx schrieb:

Ach, sorry deine Frage falsch gelesen.

Ich glaube aber, dass a vor b stehen muss, sonst gibt's halt
Zusatzregel:

<WORT> ::= {a<WORT>b}+ | {b<WORT>a}+

Hmm, wie machen wir damit abba?

'abba' machen wir gar nicht

Ist alles lange her, aber ich meine das eine Sprache {#a=#b, Reihenfolge egal}
nicht durch eine Turingmaschine berechent werden kann und daher
nicht durch eine kontextfreie Sprache dargestellt werden kann.

Ist aber alles ohne Gewähr.

Ponto

Eine Turingmaschine ist dafür relativ einfach anzugeben.

Aber was ist mit: <WORT> ::= <WORT>a<WORT>b<WORT> | <WORT>b<WORT>a<WORT> |

Jester

Wie wär's damit

<WORT> ::= <WORT><WORT> | a<WORT>b | b<WORT>a | ab | ba

das funktioniert auf jeden Fall.

@Jockelx: Du verwechselst da was. Turingmaschinen können alles berechnen was berechenbar ist. (churchsche These). Echt Kontextfreie Grammatiken können aber nicht mehr von endlichen Automaten erkannt werden. Man benötigt dazu einen Automaten mit Stack.

Der funktioniert übrigens ziemlich einfach. Der Stack ist anfangs leer. Immer wenn der Stack leer ist, kann die Maschine in den Endzustand wechseln. Wenn sie ein a oder b liest, schaut sie auf dem Stack nach, ist dort der gleiche Buchstabe, dann legt sie ihn einfach obendrauf, ist dort der andere Buchstabe, so löscht sie ihn runter.

MfG Jester

Prof84

Blue-Tiger schrieb:

Moin! Ich hab da ein kleines Problem mit einer Aufgabe, die uns von unserm Professor aufs Auge gedrueckt wurde... leider ohne uns ueberhaupt eine gute (oder auch nur zusammenhaengende) Beschreibung der Backus-Naur Form zu geben...
Im Netz find ich leider keine ausreichend detailierte Beschreibung der BNF (nach 1-2 Seiten gehts immer ueber in Parsing-Regeln und Compilerbau). Vom Buch, das uns als Skriptum empfohlen wurde, haben uns Hoehersemestrige abgeraten, also sitz ich vorerst mal mit recht mageren Infos um die BNF zu Hause rum... wer also Tutorials oder eBooks oder sonstige Hinweise kennt, dem waer ich dankbar!

http://de.wikipedia.org/wiki/BNF
http://userpage.fu-berlin.de/~ram/pub/pub_kfd8tk89g/programmieren_bnf_de

Witzig wie sich manchmal alles zusammenfügt. Ich grübel grade über ABNF :
http://w3.org/TR/2004/REC-speech-grammar-20040316/#S4.15