Formale Grammatik: Recht- linkslineare Grammatik.

[Schattentanz]

Hi,
habe gestern mit jemand ein bisschen theoretische Informatik gebüffelt und wir kamen dann irgendwann bei den Grammatiken nicht weiter. Im Prinzip kein Hexenwerg, vielleicht weiß hier jemand darüber Bescheid.

Gegeben sei die rechtslineare Typ3-Grammatik G durch Σ ={a,b} und V ={A,B,S} sowie 
P = { A →ε,  A → aA, S → aB, B → bA} und dem Startsymbol S.

Jetzt würde ich diese Grammatik gerne in eine linkslineare überführen ohne den Umweg über einen Automaten zu gehen. Also:

 A → Aa
A → Ab
B → Ba

Was wird aus dem A →ε? Das muss ja mein neuer Startzustand sein, oder?
Also X → A?

 

[langfingerli]

 

[Schiffversenker]

Vielleicht sollte man die Frage in ein Pro-Forum verschieben?

Ich hab zwar auch, wie vermutlich langfingerli, nicht die geringste Ahnung, worum es geht - aber mich würd's interessieren.
Vorausgesetzt man erklärt's für Leute wie mich… (gibt's vielleicht einen Link für was ganz Simples, Einführendes?)

Wichtiger, viel wichtiger wäre aber, wenn die kompetenten Forumsmitglieder Antworten liefern könnten, die Schattentanz helfen.

 

[Schattentanz]

Vielleicht sollte man die Frage in ein Pro-Forum verschieben?

Ich hab zwar auch, wie vermutlich langfingerli, nicht die geringste Ahnung, worum es geht - aber mich würd's interessieren.
Vorausgesetzt man erklärt's für Leute wie mich… (gibt's vielleicht einen Link für was ganz Simples, Einführendes?)

Wichtiger, viel wichtiger wäre aber, wenn die kompetenten Forumsmitglieder Antworten liefern könnten, die Schattentanz helfen.

Im geht um formale Sprachen. Das sind Sprachen die man unter anderem in Informatik oder in der Mathematik verwendet.
C waere auch eine. Wie 'normale' Sprachen haben Formalen auch eine Grammatik.
Mit Grammatik kann man Woerter ableiten die zur Sprache gehoeren.

In meinem Beispiel oben bezeichnet das Σ das Alphabet. Also die Buchstaben 'a' und 'b'. Darunter stehen quasi die Regeln (P) der Grammatik.
Woerter die in der Sprache (L) waeren z.B. "{ aba, abaa, abaaa }" Als Regex: aba*.

Solchen Kram braucht man z.B. beim Compilerbau und lernt man fuer gewoehnlich im Informatikstudium.

Hoffentlich hab ich das jetzt falsch erklaert. Nach den Regeln des Internets muesste ja jetzt jemand kommen der es Besser weiss.

 

[electricdawn]

C selbst ist keine formale Sprache. Formale Sprachen sind praktisch Metasprachen, die - wie @Schattentanz schon sagt - zur Definition der Sprache selbst benutzt werden.

Ich hoffe mal jedenfalls, dass ich das so noch richtig in Erinnerung habe. Ich habe mich damit Ende der Achtziger bis Anfang der Neunziger beschäftigt, und auch versucht eine eigene Sprache und einen Compiler dazu zu programmieren. EBNF wird zum Beispiel für Sprachendefinitionen benutzt.

Aber ich bin da bestimmt auch nicht der Fachmann für.

PS: Ich glaube, ich liege falsch damit, das C keine formale Sprache ist...

 

[Haskelltier]

Du hast ja schon richtig erkannt, dass der reguläre Ausdruck aba^* die gleiche Sprache erzeugt. Daraus eine linkslineare Grammatik abzuleiten sollte nicht wirklich schwer sein (einfach alle Worte beginnend von rechts erzeugen). Ich schreib mal in Pseudo-LaTeX. Startzustand ist wieder S:

S -> A\epsilon
S -> Sa
A -> Bb
B -> a

 

[Schattentanz]

C selbst ist keine formale Sprache. Formale Sprachen sind praktisch Metasprachen, die - wie @Schattentanz schon sagt - zur Definition der Sprache selbst benutzt werden.

So wie ich das im Kopf hatte ist C eine formale Sprache. Genau genommen dachte ich C sei eine kontextfreie Sprache (Typ-2-Sprache).

 

[Haskelltier]

C selbst ist keine formale Sprache. Formale Sprachen sind praktisch Metasprachen, die - wie @Schattentanz schon sagt - zur Definition der Sprache selbst benutzt werden.

Die meisten Programmiersprachen lassen sich mit einer kontextfreien Grammatik beschreiben.

PS: Ich glaube, ich liege falsch damit, das C keine formale Sprache ist...

So ist es.

 

[Schiffversenker]

Das mit dem "formalen Sprachen" … ist klar.
Wenig Kenntnisse davon, duster noch ein wenig im Hinterkopf. Mal ein angefangenes Seminar in den Achtzigern.
Nur das mit den links-/rechtsdrehenden Grammatiken … da klingelt so gaaaaar nichts mehr.
Außer was in der Biochemie.