Sprache in Syntaxdiagramm < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:33 So 17.02.2008 | | Autor: | svenchen |
Einen schönen Sonntag zusammen,
ich habe mir eben auf
![[]](/images/popup.gif) http://www.fsg-marbach.lb.bw.schule.de/projekte/info2000/kurs/sdiagramm.html
erarbeitet, was ein Syntaxdiagramm ist.
Jezt weiß ich allerdings nicht, wie ich folgende Aufgabe lösen könnte, mir fällt nicht ein, wie ich diese Aufgabe angehen kann:
Um Wegbeschreibungen anzugeben, sollen die Buchstaben {l,r,g} für links, rechts und geradeaus stehen. Die Buchstabenkette llgrr steht also für die Wegbeschreibung zweimal links, geradeaus, zweimal rechts.
Im folgenden sei die Sprache L definiert als die Menge aller Wegbeschreibungen, bei denen gleich oft nach links und nach rechts abgebogen wird, z.B. lr [mm] \inL, [/mm] ll [mm] \not\in [/mm] L.
Zeichnen Sie ein Syntaxdiagramm, das die Sprache L beschreibt.
Es wäre nett, wenn ihr mir sagen könntet, wie man die Aufgabe löst.
Klar, man beginnt, indem man einen Weg wählen kann:
|--->---L-----
---> |-----
|--->---R-----
Aber wie deckt man ab, dass man genau so oft liks, wie auch rechts geht?
Danke schön!
Grüße,
Sven
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:55 So 17.02.2008 | | Autor: | bamm |
Also meiner Meinung nach ist so etwas wie llrr nicht mit einem Syntaxdiagramm zu lösen. Aber vielleicht hat ja noch wer anders dazu eine Idee. Hingegen sowas wie lgr oder lrgrl sollte lösbar sein. Ich würde dabei so anfangen wie du, allerdings am Anfang erst noch eine Optionale Wiederholung von g einfügen (Wiederholung kann ja auch null mal sein), dann nach dem l bzw. r wieder eine Optionale Wiederholung von g und dann ein r bzw. l danach. Dann wieder eine Optionale Wiederholung des Ganzen, also ein Pfeil zurück zum Anfang (also vor g).
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:58 So 17.02.2008 | | Autor: | svenchen |
Hi, es wäre echt schön, wenn jemand ein solches Diagramm mir zeigen könnte.
Ich würde es gerne selbst machen, habe aber keine Idee. Ich habse schon alles versucht, aber es funktioniert einfach nicht. Ich weiß nicht, wie man das machen könnte ;(
Danke ;)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:27 So 17.02.2008 | | Autor: | bamm |
Schau dir mal das Bild unten an. Bei dem einen g musst du noch so einen Wiederholungspfeil machen wie unten drunter beim anderen g (ging irgendwie im Grafikprogramm nich mehr vernünftig). Wie gesagt, evtl. geht sowas wie llgrr auf anderem Wege. Mir fällt da gerade ein, evtl. könnte man eine rekursive Definition dazu nutzen, indem man ein Nichtterminalsymbol pfad o.ä. einführt und dieses Symbol dann in einem zweiten Syntaxdiagramm rekursiv definiert. Hattet ihr sowas schon?
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:30 So 17.02.2008 | | Autor: | svenchen |
Zunächst vielen vielen Dank für deine Skizze.
Aber ll kann man da ja nicht abgehen, wie du meinst, oder?
Was meinst du genau damit?
Könntest du mir noch zeigen, wie du meinst, dass es alternativ geht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:26 So 17.02.2008 | | Autor: | bamm |
Um ehrlich zu sein ist mir das jetzt zu blöd meine zweite Idee nochmal komplett zu zeichnen :). Aber die Idee ist folgende: Man nimmt das erste Diagramm von oben und ersetzt jeweils die l und r Knoten durch ein Nichtterminalsymbol pfadl bzw. pfadr. Nichtterminalsymbole werden als Rechteck gezeichnet. Jetzt zeichnest du noch zwei weitere Syntaxdiagramme für diese Nichtterminalsymbole, die dann ungefähr so aussehen (jetzt nur mal für pfadl):
|-[pfadl]-- -------
| | | |
| | | |
----(l)---------(g)----(r)--
| |
| |
-------
Du definierst also pfadl rekursiv, d.h. das Nichtterminalsymbol pfadl enthält wieder pfadl für weitere Wiederholungen von l (falls nötig). Und damit sollte das dann funktionieren...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:58 So 17.02.2008 | | Autor: | svenchen |
bamm, herzlichen Dank. Ich hab das jetzt weitgehend verstanden.
Hast mir sehr viel geholfen :)
Danke !!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:25 Mo 18.02.2008 | | Autor: | svenchen |
Hallo, ich habe noch eine weitere Frage.
Und zwar bin ich nun dabei, das ganze in EBNF darzustellen.
Der Übersicht halber habe ich das ganze nochmal gemacht:
[Dateianhang nicht öffentlich]
Ich dachte ich fange mit dem rot markierten Teil an.
Jedoch tauchen da schon Probleme auf :/
Weg -> ('g' | ' ') { ' ' ('g' | ' ') }
wäre das so okay ?
'' steht für einen Weg, der nur einer Linie entspricht, wo kein Symbol drin ist.
das , was in der Klammer { } steht ist die Rückverbindung.
So wie ich das verstehe steht dann in der Klammer als erstes der leere Weg, der ja die Rückverbindung ist.
Als zweites dann alles, wo diese Wückverbindung draufzeigt, was ja der hinweg ist.
Ich habe mich jetzt nur auf den rot markierten Teil bezogen.
Stimmt das so, oder wie würdet ihr an diese Aufgabe rangehen?
Das ganze ist übrigens eine alte Klausuraufgabe mit 5 Punkten.
Es wäre schön, wenn ihr mir helfen würdet ;)
Danke!
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
|
| |
|
Hallo,
der gesamte rote Teil in deinem Syntaxdiagramm bedeutet, dass 'g' beliebig oft wiederholt werden darf, insbesondere auch keinmal - also kurz in EBNF: {'g'}. Alternativen via | musst du nur bei echten Verzweigungen des Diagramms (wie sie dann im nächsten Schritt auftreten werden) definieren.
Jedoch hast du dir die Aufgabe ein wenig erschwert, finde ich, indem du recht viele Nichtterminale definiert hast. In diesem Fall wäre es meiner Meinung nach übersichtlicher, es bei einem Nichtterminal weg zu belassen: Die Idee ist, dass nach jedem vorkommenden 'l' - nach einer beliebigen (auch beliebig langen) Folge von weiteren zulässigen Terminalen (oder auch keinem) - genau ein 'r' folgt, an das wieder eine beliebige Zeichenfolge anknüpft. In BNF-Notation z.B.: l { <weg> }* r { <weg> }* (Die übrigen Fälle sowie das Aufschreiben in EBNF überlasse ich dir, sofern du magst.)
Ich bin mir ehrlich gesagt auch nicht ganz sicher, ob die durch dein Syntaxdiagramm erklärte Grammatik völlig der geforderten Spezifikation genügt. Wenn ich es richtig lese, kannst du z.B. nicht llrr erzeugen, obwohl dieses Wort in der Sprache enthalten ist. (Wenn du im L-Diagramm den Pfad zur Rekursion einschlägst, hast du ja noch gar kein 'l' gesetzt, d.h. im Prinzip fährst du doch da im Leerlauf.) Auch das leere Wort fehlt.
Grundsätzlich würde ich auch raten, klare Bezeichnungen einzuführen und insbesondere Nicht-Terminalen stets anderen Namen zu geben als Terminalen (die du auch nicht umbenennen solltest, wenn sie bereits in der Aufgabenstellung benannt wurden). Dadurch wird es gerade bei komplexeren Diagrammen verständlicher.
|
|
|
| |
|
@Demokrit
Danke für deine Antwort.
Ich mache das gerne selber. Allerdings weiß ich im moment leider noch nicht genau, was ich machen soll ;(
Was meinst du mit dem * in deiner BNF Form?
Wie meinst du, sollte das Syntaxdiagramm aussehen?
Ich komm der Beschreinung leider nicht ganz nach.
Danke ...
|
|
|
| |
|
Hallo,
der Kleene-Stern (*) besagt nur, dass das in den geschweiften Klammern beliebig oft (insbesondere auch keinmal) wiederholt werden darf - in der EBNF-Form lässt man ihn dann einfach weg. Ich zielte darauf ab, mit nur einem Nichtterminal weg zu operieren. Dies funktioniert z.B., indem man das Links-Abbiegen (diesmal in EBNF) so definiert: 'l' {weg} 'r' {weg}. Rechts-Abbiegen: 'r' {weg} 'l' {weg} Geradeaus: 'g' {weg}. Leeres Wort: [mm] \varepsilon
[/mm]
Vielleicht kannst du daraus das Syntaxdiagramm schon selbst ableiten.
Der Weg mit zwei Nichtterminalen, den du jetzt in deinem neuen Syntaxdiagramm eingeschlagen hast, ist natürlich genau so richtig, deswegen solltest du am besten auch auf deiner Route weitermachen. Viel fehlt ja ohnehin nicht mehr. :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:25 Do 21.02.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:14 Di 19.02.2008 | | Autor: | svenchen |
Ich habe das ganze nochmal geändert, in Anlehnung an den letzten Beitrag.
Wäre das eine richtige Lösung? Ist aber immer noch ganz schön lang...
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
Hallo,
ja, das sieht schon recht gut aus. Ein paar Kleinigkeiten noch:
(i) Derzeit kannst du vor jedem "Abbiegen" (li/re) stets nur einmal oder keinmal gerade aus gehen - es muss aber beliebig oft gehen, du brauchst also eine volle Schleife. Du musst also einfach noch eine Rückverbindung beim ersten 'g' einbauen und beim letzten dann genau so.
(ii) Das leere Wort ist weiterhin nicht erzeugbar. Du brauchst also auch einen Pfad, der ohne irgendwelche Terminale zu produzieren vom Anfang zum Ende geht. (Man kann ihn geschickt oder ungeschickt wählen.)
(iii) Die beiden inneren "Knoten" (innerhalb von li/re bzw. re/li) können vereinfacht werden (zudem ist auch hier noch das Problem, dass du z.B. nicht 'ggg' setzen kannst): Wenn du den "leeren Pfad" aus (ii) geschickt wählst, kannst du ausnutzen, dass 'g' durch weg erzeugt werden kann. Dann brauchst du bloß noch je eine weg-Schleife im Inneren einbauen und bist fertig.
|
|
|
|
