Hi Leute, ich muss mich grad auf mein Abitur vorbereiten und da kommen immer neue Fragen auf. Hier nun die aktuellen zu den formalen Sprachen:

Def. A,B,C=NichtTerminale +,-,*,/=Terminale

Typ0 Grammatik:
- Alles möglich, solange entweder Rechts oder Links ein nichtterminals Zeichen besteht
(oder muss das NT auf der linken Seite sein??)
- Turingmaschine

Typ1 Grammatik:
- keine Verkürzung und außerdem mindestens ein NT auf der linken Seite?
- Turingmaschine mit endlichem Band

Typ2 Grammatik:
- links muss genau ein NT stehen, rechts egal
-Kellerautomat

Typ3 Grammatik:
- linkslinear wenn einem NT -> NT & T zugeordnet wird
- rechtslinea wenn einem NT -> T & NT zugeordnet wird
- welcher Automat?

Zu den Fragen:
1. Bin ich mir nicht sicher, ob das so stimmt und würde gerne eure Meinung wissen. Außerdem weiß ich nicht, warum das eine eine endliche Turingmaschine darstellt und das andere einen Kellerautomaten.
Kann mir das jemand auf deutsch erklären ?

Danke und bis bald!
Grüße Sylvus


//edit
Wenn mein Lehrer jetzt die Aufgabe stellt:
Erstelle eine Sprache, die alle Wörter der Form a³b³c³ beinhaltet, kann ich dann von folgenden Sachen ausgehen:
- Die Sprache darf auch andere Wörter wie a²b²c² enthalten
- a³ mein aaa, oder muss ich das als eine Regel definieren?

Grüße


Moderiert von Narses: Topic aus Sonstiges (Delphi) verschoben am So 02.05.2010 um 12:54

Ich denke diese Vorlesungsfolien werden dir weiterhelfen:

Übersicht über die Chomsky-Hierachie
Grammatiken
Turingmaschienen

lg elundril

P.S.: Kann es sein das du in deinem Edit Sprachen und Grammatiken verwechselst?

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

hi, hier auch noch 2 links von mir
Find ich persöhnlich gut!
Formale Sprachen
Chomsky Grammmatik Interpreter

Kongrete Erklärungen, so finde ich, würden den Rahmen des Forums sprengen!?

Gruss Alf

Hi,
also schonmal Danke für die Hilfe, allerdings will ich doch mal wissen, ob meine Interpreationen richtig sind.

@ALF:
Der Chomsky Grammatik Interpreter scheit nicht zu gehen, da dies nicht als eine Typ1 Grammatik erkannt wird:
www.logn.de/chomsky/...&_P=xy-%3Eyx#end

@elundril
Danke für deine Folien. Nein ich dachte an folgendes:
Eine Grammatik die Wörter der Art a³b³c³ aktzeptiert wäre:
G={(x;y;z),(a;b;c),P,x}
P={ x-> ax; x->ay; aaa->a³;
y-> by; y->bz; bbb->b³;
z-> cz; z->c; ccc->c³;}

Damit wäre in meinen Augen die Aufgabe erfüllt. Dies wäre außerdem(bis auf aaa->a³; bbb->b³; und ccc->c³) eine Typ2 Grammatik richtig?

@All
Ich hab das ganez ja verstanden, nur bin ich mir bei einzelnen Sachen nicht sicher und erkenne das auch nicht aus den Folien, Wikipedia oder anderen Sekundärquellen, darum frag ich ja!
1) Müssen links immer NUR Nichtterminale stehen?
Oder können da auch terminale stehen?
2) Bei Typ1 kann ich doch unendlich lange Wörter bilden, warum reicht mir trotzdem eine endliche Turingmaschine?
3) Wieso beschreibt Typ2 einen Kellerautomaten?
4) Typ3 beschreibt auch einen Typ von Automat, welchen?


Danke!

Sylvus hat folgendes geschrieben :

Danke für deine Folien. Nein ich dachte an folgendes: Eine Grammatik die Wörter der Art a³b³c³ aktzeptiert wäre: G={(x;y;z),(a;b;c),P,x} P={ x-> ax; x->ay; aaa->a³; y-> by; y->bz; bbb->b³; z-> cz; z->c; ccc->c³;} Damit wäre in meinen Augen die Aufgabe erfüllt. Dies wäre außerdem(bis auf aaa->a³; bbb->b³; und ccc->c³) eine Typ2 Grammatik richtig?

Also willst du eine Grammatik definieren die die Sprache bestehend aus dem Wort a³b³c³ erzeugt. Prinzipiell würde ich das dann so angehen:
G = <{A}, {a,b,c}, P, A}
P = {A -> a³b³c³}

und fertig. Weil deine Sprache ja nur aus einem Wort besteht passt das. Die Grammatik wäre sogar n Typ-3-Grammatik, also regulär.

Was mir an deiner auffällt ist das du plötzlich auch terminalsymbole ableiten willst. Warum? a³ ist ja nur ne Kurzschreibweise für aaa. Da musst du nix Produzieren oder umwandeln.

Wenn die Definition für die Sprache vom Professor aber so aussieht: L = {a^n b^n c^n | 0 < n <=3} dann wirds kompliziert denn die Sprache wäre dann nicht mal mehr Kontextfrei. Die wäre dann wohl Kontextsensitiv.

Sylvus hat folgendes geschrieben :

@All Ich hab das ganez ja verstanden, nur bin ich mir bei einzelnen Sachen nicht sicher und erkenne das auch nicht aus den Folien, Wikipedia oder anderen Sekundärquellen, darum frag ich ja! 1) Müssen links immer NUR Nichtterminale stehen? Oder können da auch terminale stehen? 4) Typ3 beschreibt auch einen Typ von Automat, welchen? Danke!

ad 1) Kommt auf den Grammatiktyp an. Bei Kontextfrei und Regulär ja, bei Monoton, Kontextsensitiv und alles darunter nein.

ad 4) Typ-3 sind reguläre Grammatiken. Diese können durch einen minimalen Deterministischen Endlichen Automaten (DEA) dargestellt werden. Da man jeden Nicht-Deterministischen Endlichen Automaten (NEA) in einen DEA umwandeln kann, ist es doch eigentlich egal was für ein Automat.

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Ok also können bei Typ1 und Typ0 links auch Terminale stehen!
Können links auch NUR Terminale stehen, oder muss mindestens ein NT dabei sein?

Außerdem muss ich mich dann verbessern. Ich will z.B. Eine Sprache mit den Wörtern der Form a^n b^n c^n mit n>2.
Dann wäre soetwas wie:
G={(x;y;z),(a;b;c),P,x}
P={ x-> ax; x->ay;;
y-> by; y->bz;;
z-> cz; z->c;}

durchaus richtig oder?
Aber schonmal vielen Dank, langsam versteh ich alles^^

Nein, das wäre a^i b^j c^k (jeweils >= 1). Deine Aufgabe ist das Paradebeispiel kontextsensitiver Sprachen .

ok also wenn ich eine Grammatik aufstelle darf diese dann auch nur diese Wörter zulassen? Weil meine Grammatik hätte ja beides sowohl a^i b^j c^k und a^n b^n c^n einfach als Sonderfall i=j=k!
Oder muss das aus der Aufgabenstellung hervorgehen? Grüße

P.S. die anderen Fragen:
1) Können links auch NUR Terminale stehen, oder muss mindestens ein NT dabei sein?
2) Bei Typ1 kann ich doch unendlich lange Wörter bilden, warum reicht mir trotzdem eine endliche Turingmaschine?
3) Wieso beschreibt Typ2 einen Kellerautomaten?

deine frage zu a^i b^j c^k verstehe ich leider nicht wirklich. könntest du sie umformulieren und näher erläutern?

ad 1) es muss mindestens 1 NonTerminal links stehen, sonst kannst ja nix ableiten. Terminal heißt das da aus is mim ableiten. Terminalsymbole können nur in Lindenmayersysteme abgeleitet werden, aber dieses systeme haben auch keine Terminale.

2 und 3 weiß ich leider nicht. aber ich glaube folgendes:

du kannst keine unendlich langen wört produzieren. die Wörter die deine Sprache produziert ist immer endlich, da du ja produktionen nur endlich oft anwendest. zb ist a^n b^n c^n eine Typ-1-Sprache. n ist in diesem Fall aber endlich ja du ja irgendwann mit den Produktionen der grammatik aufhören musst. Also wäre das eingabeband der Turingmaschienen immer endlich.

Vielleicht meinst du linear beschränkte Turingautomaten bei denen das Arbeitsband höchstens so lang ist wie das Eingabeband. Diese akzeptieren nämlich nur Typ-1-Sprachen. Ohne diese bedingung akzeptieren Turingmaschienen auch Typ-0-Sprachen.

warum das nun so ist kann ich dir auch nicht sagen, aber ich denke, wenn man das nicht mal an der uni lernt, warum das so ist, solltest du es auch nicht können müssen für dein abitur.

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

ich meinte nur, dass ich ja ne Grammatik machen kann, die viel mehr Wörter beinhaltet, aber auch die gewünschten. Ich wusste nicht, ob das auch zulässig ist, weil ich dann ja auch soetwas wie a^n b^n c^n erstellen kann. Nur zusätzlich z.B. auch a^1 b^2 c^30 oder so

Vielen Dank für die Antworten!

hmmm, das solltest du mal deinen Lehrer fragen, aber in der uni war bei uns immer so die regel das wenn steht "Geben sie eine Grammatik an die diese Sprache erzeugt", gemeint ist, "Gib eine Grammatik an die genau diese Sprache erzeugt und nicht auch noch andere Sprachen". Ob das nun allgemein gilt oder nur inoffiziell war, weiß ich nicht, aber ich denke du bist auf der sichereren seite wenn du die strenge Einschränkung nimmst, mit einer Grammatik die genau das erzeugt und nicht nur als Teil einer anderen Sprache.

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Sylvus hat folgendes geschrieben :

ok also wenn ich eine Grammatik aufstelle darf diese dann auch nur diese Wörter zulassen?

Überlege doch einmal, sonst wäre Σ* immer eine richtige Grammatik. Ziemlich langweilig, oder ?

ist Σ* nicht ein Alphabet, also eigentlich ne Sprache und keine Grammatik?

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Stimmt, du bist ja auch der Student . Aber dafür eine Grammatik zu entwerfen, ist trotzdem ein wenig einfacher als für a^n b^n c^n.