Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
249 Aufrufe
Guten Tag,

noch eine Frage bezüglich das Angeben von Grammatiken.

Ich finde es einfacher aus einem Automat, die Grammatik zu konstruieren aber manchmal ist ´der Automat nicht vorgegeben, kompliziert herzustellen oder in der nächste Frage als Antwort zu geben.

Meine Frage ist:

Gibt es eine ''Strategie''/ Vorgehensweise um die Grammatik  zu konstruieren oder versucht man mit Bspielwörter nur.

Zum Beispiel habe ich die Lösungen von Aufgabe 30 und 31 (REC-AB und REC-AC) verstanden, ich konnte aber die nicht selbst lösen.
bezieht sich auf eine Antwort auf: Grammatik angeben
in REC-AB von uodys uodys Lernwillige(r) (870 Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

Man braucht dafür vor allem viel Übung. Es gibt für einzelne Grammatiktypen so ein paar Standard-Vorgehensweisen:

  • Grammatiken vom Typ 3 werden im Prinzip genauso wie endliche Automaten konstruiert. Da kann man sich wirklich jedes Nonterminalsymbol wie den Zustand eines EAs vorstellen und sich so durch die Produktionen hangeln. Produktionen, die auf $\lambda$ gehen, entsprechen dabei Endzuständen. (Siehe auch Lehrbuch, Seite 188, zur Sprachmächtigkeit rechtslinearer Grammatiken.)
  • Kontextfreie Grammatiken können schon deutlich komplexere Strukturen erzeugen, ein typisches Konstrukt dabei sind aber Regeln von diesem Typ:
    $X \rightarrow AXB$
    Sie erzeugen so eine geschachtelte "Klammerstruktur", wenn man sich $A$ als Klammer-Auf vorstellt und $B$ als Klammer-Zu. Man kann das auch mit anderen "Klammertypen" $C$ und $D$ kombinieren - das wird vor allem zum Parsen von Programmiersprachen oft benötigt. Eine zweite typische Struktur ist:
    $Y \rightarrow AYA | BYB$
    Auf diese Weise erhält man Palindrom-artige Wörter.
  • Bei monotonen Grammatiken schließlich ist eine typische Vorgehensweise, dass man zweistufig
    • zuerst die richtige Anzahl an Zeichen erzeugt
    • und danach die Zeichen an die richtige Position sortiert.

Das sind natürlich nur einige wenige Möglichkeiten bei der Grammatik-Konstruktion - je kleiner der Grammatik-Typ ist, desto mehr kann man damit machen. Schon monotone Grammatiken sind so mächtig, dass man sich kaum Sprachen vorstellen kann, die durch sie nicht definiert werden können (und bei allgemeinen Grammatiken sind dann der Phantasie (fast) keine Grenzen gesetzt). Es ist also wichtig, dass Sie viel üben, um routiniert mit Grammatiken umgehen zu können! Aber die obigen Standardstrukturen sind schon einmal ein guter Einstieg - viel darüber hinaus machen wir in der Vorlesung ja auch nicht...

Aber überlegen Sie bspw. mal, wenn Sie diese Standardstrukturen schon gut beherrschen, wie eine monotone (oder meinetwegen auch allgemeine) Grammatik für die Sprache der Wörter vom Typ $$a^nb^{2^n}$$ aussehen könnte. Das ist gar nicht so leicht, aber man lernt viel dabei. (Ich glaube, wir haben in irgendeiner Übungsaufgabe auch die Lösung dafür.)

von Dozent (10.1m Punkte)  
0 0
Vielen Dank für Ihre schnelle und ausführliche Antwort !
Ja es ist sehr ähnlich zu SAA-1-3.
Hier würde ich so machen : Man braucht eine kontextfreie Grammatik mit P= { S'--> S| lambda,
       S --> ABB|ASBB,
       A --> a,
       B --> b}
0 0
oder einfach {S--> ASBB|lambda,
                   A-->a,
                   B-->b}
Kommt darauf an welcher Grammatiktyp verlangt wird.
0 0
Da fehlen Ihnen aber noch die $c$'s...
0 0
Das war die Antwort für die Sprach a hoch n b hoch 2n
0 0
Nicht $a^nb^{2n}$, sondern $a^nb^{2^n}$. Das ist ein großer Unterschied!

Wichtiger Tipp für die Klausur (ganz im Ernst): LESEN Sie die Aufgaben genau durch! So viele Punkte gehen verloren, weil Leute die Aufgaben falsch verstanden haben.
0 0
Hallo,

Sie haben Recht.
Hier ist ein Versuch von mir bzgl a hoch n b hoch 2 hoch n;
Diese ist aber keine monotone Grammatik wegen Lambda:
{S-->KXBY,
 K-->aK|lambda,
 X-->XD|lambda,
 DY-->Y,
 Y-->lambda,
 DB-->BBD,
 B-->b}

Ich bedanke mich
0 0
Auf den ersten Blick sieht diese Grammatik gar nicht so schlecht aus - aber wenn man sie in den XWizard eingibt, kommen doch viele falsche Wörter heraus: http://www.xwizard.de:8080/Wizz?template=ID-C22148

Vielleicht schaffen Sie es ja noch, sie zu korrigieren?
0 0
Geben Sie aber bitte zum Herumprobieren in den declarations eine kleinere "maxdepth" ein (vielleicht 10 oder so).
...