Informatik - Chomsky Hierarchie - Typ 2 / Typ 3 Grammatiken ...

T

Try_AND_Solve

0
Guten Morgen zusammen...

gegeben sei folgende formale Grammatik G = (N, T, P, s) , mit

N = {GZAHL, ZIFFER, GZ, ZAHL}
T = {0,1,2,3,4,5,6,7,8,9}
P = {GZAHL -> GZ | ZAHL GZ,
ZAHL -> ZIFFER | ZIFFER ZAHL,
Ziffer -> 0 | 1 | 2 | 3 | 4 | 5 | 6 |7 | 8 | 9 | ,
GZ -> 0 | 2 | 4 | 6 | 8 }
s= GZAHL.

Ich frage mich, von welchem Typ diese Grammatik ist (Typ2 ?)


Die eigentliche Frage ist aber:

Auf einem Blatt zur theoretischen Informatik, welches wir erhalten haben sind Typ3 Grammatiken definiert als

" vom Typ 3 oder regulär, wenn gegenüber Typ 2 für jede Regel einschränkend X -> y oder X -> yYgilt, wobei y € T*, X,Y € N "
Zum Vergrößern anklicken....

das verstehe ich so, dass auf der linken Seite genau ein Nichtterminal stehen muss, auf der rechten Seite beliebig viele Terminale (wegen T*). oder aber beliebig viele Terminale und ein NIchtterminal.

Diese Definition widerspricht sich aber entweder mit anderen Definitionen, die ich gefunden habe, oder ich habe die Definition oben falsch gedeutet (bin noch nicht sonderlich geübt in dieser Schreibweise)

Beispielsweise finde ich auf einer anderen Seite:

Typ 3regulär Die Regeln im Regelsystem müssen die folgende Form haben
  • img385.png
  • img386.png
  • img387.png
wobei A Nonterminal und a Terminal ist.
Zum Vergrößern anklicken....

also auf der rechten Seite entweder genau ein Terminal oder ein Terminal und ein NIchtterminal....

Ist die Blattdefinition einfach fehlerhaft ?
 
Was ich mir gemerkt habe: mit regulären Grammatiken kann man keine Verschachtelungen erkennen:
S->aSa
S->bSb
S ->x
wäre nicht regulär bzw.
<html><div>xyz</div><div><div>foo</div></div></html>
wären die "div" Tags regulär nicht erkennbar.


Andres gesagt: alle regulären Grammatiken lassen sich als NFAs implementieren. Beim Typ2 (wikipedia sagt, das wäre kontextfreie Grammatik) muss schon ein Kellerautomat mit einem Stack her.

Um zu zeigen, dass eine Grammatik nicht regulär ist bzw. nicht kontextfrei, gibt es das Pumping Lemma. Möchte mich da aber nicht wieder einarbeiten ;).
Nur als Schätzung:
man kann aus der gegebenen Grammatik sowas konstuieren:
L = {ZAHL^n GZ^n|n>0}
also einfach dass ZAHL und GZ gleich oft vorkommen und von der Grammatik erkannt werden.
Dass eine solche Sprache regulär ist, sollte sich mit dem Pumping Lemma wiederlegen lassen (oder mit der simplen Überlegung, dass man so einen Ausdruck zwar mit der gegebenen Grammatik, aber nicht mit einem RegEx erkennen kann).

Edit:
wenn ich mir das nochmal so anschaue, bin ich gar nicht so sicher, ob meine obige Ausführung (Kontra Regularität) korrekt ist.
Allerdings wäre die Regeln
GZAHL -> gz | ZAHL gz,
ZAHL -> ziffer | ziffer ZAHL,
einmal links und einmal rechtsregulär - beide können aber nicht in der gleichen regulären Grammatik auftreten.
 
Hi Try_AND_Solve,

die beiden Definitionen sagen genau das gleiche: Das leere Wort ist in T* doch enthalten, genauso wie halt sonst jedes bildbare Wort. Das entspricht also den Ableitungen A -> € und A -> a. Die dritte mögliche Form einer Ableitung ist ebenfalls bei beiden gleich: Ein Terminalsymbol (aus T*, kann also mehr als ein Buchstabe sein) gefolgt von _einem_ nicht-Terminalsymbol.
Das wäre eine rechtsregüläre Grammatik (das was gemeinhin als regulär bezeichnet wird). Für eine linksreguläre sind bei der letzten Regel Terminal und nicht-Terminal vertauscht.

Da deine Grammatik auch Regeln enthält, wo auf der rechten Seite zwei konkatenierte nicht-Terminalsymbole auftauchen, ist sie nicht regulär (Typ 3).
Sie entpricht jedoch dem Typ 2 - ist also kontextfrei.

@CDW: Nicht nur als NFAs, sondern allgemein von endlichen Automaten - also auch deterministischen :P
 
Hi,

vielen Dank für die beiden Antworten, auch wenn ich mit der ersten Antwort nicht so viel anfangen konnte, weil wir in der Stufe 13 mit nur 2 Wochenstunden nicht sonderlich in die Tiefe gehen können und Dinge wie das Pumping Lemma für mich noch ein großes Fragezeichen bilden (vielleicht hätte ich das auch dazuschreiben sollen).

Hi Try_AND_Solve,

die beiden Definitionen sagen genau das gleiche: Das leere Wort ist in T* doch enthalten, genauso wie halt sonst jedes bildbare Wort. Das entspricht also den Ableitungen A -> € und A -> a. Die dritte mögliche Form einer Ableitung ist ebenfalls bei beiden gleich: Ein Terminalsymbol (aus T*, kann also mehr als ein Buchstabe sein) gefolgt von _einem_ nicht-Terminalsymbol.
Zum Vergrößern anklicken....
Tatsächlich ging es mir nicht um das leere Wort, sondern ich habe das T* missverstanden. (Ich dachte es würde sich dabei um eine beliebige Anzahl an Terminalen handeln und nicht um ein Terminal beliebiger Länge).

Wenn ich jetzt ausdrücken wollte, dass beispielsweise x aus einer beliebigen Anzahl an Terminalen bestünde, wie müsste ich das dann aufschreiben?
 
Jetzt habe ich deine Frage nicht wirklich verstanden :D
Also wenn T dein Alphabet ist und w dein Wort, dann heisst w € T*, dass du soviele Buchstaben aneinanderreihen (konkatenieren) kannst wie du möchtest, also auch keinen (=leeres Wort). Das kleine a bzw. das kleine y in den beiden von dir geposteten Definitionen sind so zu verstehen wie das w oben.
Du kannst bei regulären Sprachen aus einem nicht-Terminal A nicht zwei Produktionen gleichzeitig ableiten. Du kannst dir entweder aussuchen welche du nimmst, das schreibt man dann eben zum Beipsiel so:
Code: 
Ziffer -> 0 | 1 | 2 | 3 | 4 | 5 | 6 |7 | 8 | 9 |
also die Möglichkeiten getrennt durch einen senkrechten Strich,
oder du konkatenierst die (nicht-)Terminalsymbole, also so
Code: 
A -> 12345 | 1 | 5138 | € | 1B | ...
Aber du kannst nicht plötzlich das Wort trennen in zwei neue Wörter.
Bei Typ 2 Sprachen könntest du allenfalls noch solche Produktionen haben:
Code: 
A -> BC
B -> ...
C -> ...
aber das geht im regulären Fall nicht.

Ich hoffe, das war was du meintest ;)

Edit: Zum besseren Verständnis des T*, hilft dir vielleicht das hier: Kleenesche Hülle
 
Zuletzt bearbeitet:
Ja, vielleicht habe ich die Frage etwas unglücklich gestellt. Es handelte sich dabei um eine neue Frage, die nichts mit den vorher gestellten Fragen zu tun hatte und die sich nicht auf Typ3-Grammatiken bezogen hat (die Ursprungsgrammatik war ja auch vom Typ2).

Ich wollte einfach nur eine mathematisch korrekte Schreibweise haben, wenn ich ausdrücken will, dass ein Nichtterminal definiert ist, als eine Folge von beliebig vielen Nichtterminalen...

Also zum Beispiel:

A -> BD CDR DWQT EZ L ... (anstatt alle Nichtterminale zu schreiben, möchte ich allgemein ausdrücken, dass hier beliebig viele Nichtterminale stehen können, die eine beliebige Länge haben, denn so hatte ich T* ursprünglich (miss-)verstanden).
 
Das ist doch überhaupt keine richtige Sprache mehr dann also bzw wäre L = T* .
Ich würde das einfach so schreiben:
Code: 
A -> B          B € N*
Formal korrekt wäre das, obwohl ich den Sinn einer solchen Produktion nicht ganz nachvollziehen kann :P
 
Muss denn im Leben immer alles einen Sinn haben? :rolleyes:

Mir ging es ausschließlich um die mathematisch korrekte Schreibweise.

Ich würde das einfach so schreiben:

A -> B B € N*
Zum Vergrößern anklicken....
würde das aber nicht bedeuten, dass A definiert ist, als ein Nichtterminal beliebiger Länge (jedenfalls war das noch weiter oben die Bedeutung!?)

Ich wollte aber ausdrücken, dass A definiert ist, als eine beliebige Folge von Nichtterminalen, die jeweils eine beliebige Länge haben dürfen...
 
Wenn N = {A,B,C,D}, dann kann Z € N* eben sowas sein: A oder CCCCCCCDDDABBBBBBAA oder sonst was.
Wonach du A,B,C und D dann ableitest ist ne andere Sache. Da kannste dann ja wieder schreiben: A -> a a € T*

Was ein nicht-Terminal beliebiger Länge sein soll weiss ich nicht.
Produktionen wie die von dir angegebene
Code: 
A -> BD CDR DWQT EZ L
Gibt es nicht!
Es könnte höchstens
Code: 
A -> BD | CDR | DWQT | EZ | L
oder
Code: 
A -> BDCDRDWQTEZL
geben.
So wie du es schreibst würden ja mehrere Wörter erzeugt, eine Grammatik erzeugt aber immer nur eins.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben