Formale Sprachen -> Grammatik

[WarSlash]

Ich habe hier ne Aufgabe. Nur ich weiß nicht, ob diese Gramatik dazu richtig ist. Ich könnte zwar die Bespiele erzeugen, jedoch ist es möglich auch falsche Ergebnisse zu erzeugen.

Vollständig geklammerte arithmetische Ausdrücke
Erstellen Sie eine Grammatik für die Sprache aller vollständig geklammerten arithmetischen Ausdrücke über dem Alphabet {0,1,...,9,(,),+,*}.

Bsp:
S->(A | (S

A-> 0B|..|9B

B-> +C| *C

C-> 0D|..|9D

D-> ) | +S | *S | )D

Bsp:
S->(A -> (2B -> (2+C -> (2+5D -> (2+5)

S-> (S -> ((A -> ((2B -> ((2+C -> ((2+5D -> ((2+5)D -> ((2+5)*S-> ((2+5)*(A - > ((2+5)*(2B -> ((2+5)*(2+C -> ((2+5)*(2+5D -> ((2+5)*(2+5D -> ((2+5)*(2+5)D -> ((2+5)*(2+5))

jetzt kann ich einfach mit *S weiter machen. Aber es verstößt gegen die Vorschrift.

Wie man sieht, kann die Sachen alle erzeugen, aber eben die eine Sache da.
(2+5)*(2+5) wäre nicht drin, jedoch aber ((2+5)*(2+5))

Ist die Gramatik richtig und muss nur am Anfang aufgepasst werden, was man will oder ist die Gramatik völlig falsch?

[del_4901]

Ist das absicht, das die Gramatik rechtslinear sein soll? (das geht nämlich nicht ... weil dann könnte man auch die Sprache 1^n + 2^n in einem FSM implementieren ... und das geht bekanntlich ned) Aber eine CFG (meinetwegen auch in CNF) die das erfüllt ist eigendl. ganz einfach.

BTW: Gegenbeispiel
S -> (S -> ((A -> ((0B -> ((0+C -> ((0+0D -> ((0+0)

[WarSlash]

Ist das absicht, das die Gramatik rechtslinear sein soll? Weil eine CFG die das erfüllt ist eigendl. ganz einfach.

BTW: Gegenbeispiel
S -> (S -> ((A -> ((0B -> ((0+C -> ((0+0D -> ((0+0)

Absicht wars nicht, nee eher ein Fehler. Denn sowas wie
((5*(5+9)) soll ja auch gehen.

Hast du nen anderen Vorschlag. Ich komme einfach nicht mehr weiter.

Was nun?

[del_4901]

Absicht wars nicht, nee eher ein Fehler. Denn sowas wie
((5*(5+9)) soll ja auch gehen.

Hast du nen anderen Vorschlag. Ich komme einfach nicht mehr weiter.

Was nun?

Mein Vorschlag, nimm nicht die Definition von einer rechtslinearen CFG um die Gramatik zu bauen ... wie gesagt das geht nämlich nicht. Und die eigendliche Lösung ist so pipi ... die kann ich dir nicht sagen... dafür ist TI einfach zu wichtig ... da muss man selber drauf kommen, damit man sich das merkt ... da hat man wirklich mehr davon.

http://en.wikipedia.org/wiki/Context-free_grammar

[WarSlash]

Mein Vorschlag, nimm nicht die Definition von einer rechtslinearen CFG um die Gramatik zu bauen ... wie gesagt das geht nämlich nicht. Und die eigendliche Lösung ist so pipi ... die kann ich dir nicht sagen... dafür ist TI einfach zu wichtig ... da muss man selber drauf kommen, damit man sich das merkt ... da hat man wirklich mehr davon.

Kannste bitte doch machen? Ich studiere TI nicht. Ist eben für ne IF GK13 am Gymnasium. Ich sitze schon ne Stunde dran und komme nicht drauf. Null Chance. So viel haben wir nämlich zu dem Thema noch nicht gehabt. Die ganzen Grundlagen wie bei TI machen wir nicht.

[Grestorn]

Mein Vorschlag, nimm nicht die Definition von einer rechtslinearen CFG um die Gramatik zu bauen ... wie gesagt das geht nämlich nicht. Und die eigendliche Lösung ist so pipi ... die kann ich dir nicht sagen... dafür ist TI einfach zu wichtig ... da muss man selber drauf kommen, damit man sich das merkt ... da hat man wirklich mehr davon.

http://en.wikipedia.org/wiki/Context-free_grammar

Warum verlinkst du dann die Lösung, wenn du erst sagst, er soll sie selber finden?! :)

Dass Theoretische Informatik wichtig sei, ist aber aber auf jeden Fall Ansichtssache.

[Grestorn]

Kannste bitte doch machen? Ich studiere TI nicht. Ist eben für ne IF GK13 am Gymnasium. Ich sitze schon ne Stunde dran und komme nicht drauf. Null Chance. So viel haben wir nämlich zu dem Thema noch nicht gehabt. Die ganzen Grundlagen wie bei TI machen wir nicht.

Lies den verlinkten Artikel. Die Lösung steht drin.

[WarSlash]

Lies den verlinkten Artikel. Die Lösung steht drin.


Ich werde daraus nicht schlau. Example 2 oder nicht? Wie übertrage ich das nun für mich? ....

[Grestorn]

Ich werde daraus nicht schlau. Example 2 oder nicht? Wie übertrage ich das nun für mich? ....

S → 1 | ... | 9 | S + S | S - S | S * S | S/S | (S)

Korrektur: Das stimmt natürlich nicht ganz, da es nur ein-Ziffrige Zahlen zulassen würde... Muss also noch etwas angepasst werden. Ist aber nicht mehr so schwer.

[del_4901]

Warum verlinkst du dann die Lösung, wenn du erst sagst, er soll sie selber finden?! :)

Dass Theoretische Informatik wichtig sei, ist aber aber auf jeden Fall Ansichtssache.

Du setzt meine Erziehungsmethoden außer kraft! Das it ja unglaublich... TI ist schon sehr wichtig ... mein Chef wollte neulich die optimale Lösung für das Rucksackproblem so finden, indem man einfach alle optimalen Lösungen sich ausgeben lässt (bzw. die optimalsten) und der Benutzer dann auswählen soll ... da muss ich mich auch erstmal an den Kopf fassen. Stell dir mal vor, dein Chef gibt dir sone Aufagabe und du sagst erstmal ... "ja klar mach ich dir" ... Ich möchte nicht Derjehnige sein, welcher die schlechte Nachricht überbringt.

@WarSlash: Wenn ich mal sonen Informatik Untericht gehabt hätte, währ ich glücklich gewesen ... wir haben nur Excel usw. scheiss gemacht mit ein bissel Niki der Roboter ... lol ... und dann sich wundern, wenn die Schüler vor lauter Langeweile die Rechner sabotieren.

[del_4901]

S → 1 | ... | 9 | S + S | S - S | S * S | S/S | (S)
Das ist ja unglaublich ... stell dir mal vor der Junge hat sone aufgabe in der Prüfung ... das ist doch glatt für nen Arsch ... sowas kann man nicht auswendig lernen.

Ich sehe, ich habe hier 2 TI Hasser. Na wartet Ihr werdet irgendwann meine Sklaven ... unter meiner Herrschaft als SW-Architekt ^^ ... Dafür wird das Ergebnis aber auch vernünftig. *auf Holz klopf*

[Grestorn]

Das ist ja unglaublich ... stell dir mal vor der Junge hat sone aufgabe in der Prüfung ... das ist doch glatt für nen Arsch ... sowas kann man nicht auswendig lernen.

Ich sehe, ich habe hier 2 TI Hasser. Na wartet Ihr werdet irgendwann meine Sklaven ... unter meiner Herrschaft als SW-Architekt ^^ ... Dafür wird das Ergebnis aber auch vernünftig. *auf Holz klopf*

ROFL. Bist Du mit Dogbert verwandt? ;)

[WarSlash]

Wir haben noch garnicht über Kontextfreie Sprachen gesprochen. Toll.

Es ist trivial, aber ich wusste nicht das man auch S-> S*S schreiben darf. Ich dachte wenn dann S -> *S | 1, etc

Lese dir die Aufgabestellung durch, du hast doch Recht Grestorn, weil nur einstelligen verlangt sind.

Aber das Problem: Wenn ich das oben nach meinem System her aufbaue, verstehe ich nicht wie ich S-> S*S interpretieren soll

Wie mache ich denn damit die Folge: ((4+7)*(4+4)) ?

Mit der Gramatik wäre auch S-> 1 möglich. Das entspricht aber nicht der Aufgabenstellung.

[del_4901]

Wir haben noch garnicht über Kontextfreie Sprachen gesprochen. Toll.

Es ist trivial, aber ich wusste nicht das man auch S-> S*S schreiben darf. Ich dachte wenn dann S -> *S | 1, etc

Lese dir die Aufgabestellung durch, du hast doch Recht Grestorn, weil nur einstelligen verlangt sind.

Aber das Problem: Wenn ich das oben nach meinem System her aufbaue, verstehe ich nicht wie ich S-> S*S interpretieren soll

Wie mache ich denn damit die Folge: ((4+7)*(4+4)) ?

Die Aufgabenstellung ist an der Stelle schwammig weil die Sprache zu ungenau definiert wurde ... ist z.B das leere Wort auch erlaubt oder nicht etc ... (In meinen Augen ist das leere Wort auch ein gültiger Klammerausdruck.)

[del_4901]

Wie mache ich denn damit die Folge: ((4+7)*(4+4)) ?

Mit der Gramatik wäre auch S-> 1 möglich. Das entspricht aber nicht der Aufgabenstellung.

S -> (S) -> (S*S) -> ((S)*S) -> ((S+S)*S) ...

1 Ist ein gültiger Klammersaudruck ... wenn man das natürlich weghaben will... kann man das auch hinbekommen.

[WarSlash]

S -> (S) -> (S*S) -> ((S)*S) -> ((S+S)*S) ...

1 Ist ein gültiger Klammersaudruck ... wenn man das natürlich weghaben will... kann man das auch hinbekommen.

Danke. Wie sieht das mit dem Zahlen aus? Werden die einfach nach der Reihefolge eingesetzt oder wie verhält sich das. Das Problem, wir habe bis nur mit rechtsregulären Grammatiken gearbeiten und von Chomsky wusste ich vorher auch nichts.

Also rechtsregulär und linksregulär sind also unmöglich, sehe ich das richtig?

[del_4901]

Danke. Wie sieht das mit dem Zahlen aus? Werden die einfach nach der Reihefolge eingesetzt oder wie verhält sich das. Das Problem, wir habe bis nur mit rechtsregulären Grammatiken gearbeiten und von Chomsky wusste ich vorher auch nichts.

Also rechtsregulär und linksregulär sind also unmöglich, sehe ich das richtig?


rechts- und linkslinear ... (weil die Syntaxbäume nach rechts bzw. rechts sich ausdehnen) Beide lassen sich in Endliche Automaten überführen ... und können somit nur Reguläre Sprachen erkennen. Die Sprachen über alle gültigen Klammerausdrücke gehören da nicht dazu.

Chomsky der alte Jude hat ein paar lustige Bücher geschrieben ... z.B "Offene Wunde Nahost" ... denkt man gar nicht ... ist politisch sehr engagiert ... das kann man auch als nicht Informatiker lesen.

[Coda]

Dass Theoretische Informatik wichtig sei, ist aber aber auf jeden Fall Ansichtssache.
Es nützt einem öfter mal was als man glaubt.