Theoretische Informatik -> Formale Sprachen -> reguläre Sprachen und EBNF

[PlaciD]

Hallo,

erstmal eine Grundsätzliche Frage:

Ist die folgende Grammatik links- oder rechts-linear (ich vertue mich da irgendwie immer und bin jetzt komplett durcheinander)?

S->Aa A->b

Nun zur eigentlichen Frage:

Ich sitze hier vor einer Aufgabe und komme einfach nicht drauf:

"Die folgenden 3 Regeln einer Grammatik geschrieben in EBNF

<identifier> ::= <letter>|<identifier><letter>|<identifier><digit>

sind nicht regulär (Chomsky Typ 3).

a) Warum nicht?
b) Klassifizieren sie diese Grammatik."

Kann mir jemand erklären, warum die nicht regulär sind? Schließlich ist nur <identifier> ein Nicht-Terminal und <letter> sowie <digit> sind Terminale. Also für mich ist die Grammatik links-linear und somit regulär.

So, ich hoffe, mir kann irgendwer helfen

Grüße,
Sebastian

 

[Tyrell]

Also, wenn eine Grammatik rechtsregulär ist, kann es nur Ableitungen geben, bei denen rechts ein Terminal oder ein Nichtterminal gefolgt von einem Terminal steht, linksregulär ist eben umgekehrt.

Ich geh mal davon aus, dass S,A,B є N und a,b є Σ, dann ist die Grammatik S -> Aa, A -> b linksregulär.


Du kannst erstmal den regulären Ausdruck für die untere Grammatik aufstellen:

letter (letter|digit)*

und bei Bedarf noch einen DFA malen, damit sollte ausreichend gezeigt sein, dass die Grammatik regulär ist. Ich sehe keinen Grund, warum sie nicht regulär sein sollte, kann es sein, dass du irgendwas vergessen hast.

 

[PlaciD]

Ich geh mal davon aus, dass S,A,B є N und a,b є Σ, dann ist die Grammatik S -> Aa, A -> b linksregulär.

Sehr schön, dann habe ich das schonmal verstanden

Du kannst erstmal den regulären Ausdruck für die untere Grammatik aufstellen:

letter (letter|digit)*

und bei Bedarf noch einen DFA malen, damit sollte ausreichend gezeigt sein, dass die Grammatik regulär ist. Ich sehe keinen Grund, warum sie nicht regulär sein sollte, kann es sein, dass du irgendwas vergessen hast.

Nein, ich habe nichts vergessen. Es verwirrt mich auch sehr.

In einer späteren Aufgabe kommt sowas ähnliches nochmal, schon wieder so verwirrend:

"Die Definition einer Programmiersprache enthalte u.a. die folgende Regel in EBNF:

<ident> ::= <letter> | <digit> | <ident> <letter> | <ident> <digit>

a) Erklären Sie, warum dies Regeln einer kontextfreien Grammatik (Typ 2) sind.

b) Erklären Sie, warum diese Regeln nicht rechts- bzw. linkslinear (Typ 3) sind."

Hier würde ich ebenfalls sagen, dass die Sprache linksregulär ist.

Can anyone help?

Sebastian

 

[Tyrell]

Hmm, also die Sprache sieht ebenfalls regulär aus. Wenn man die verkürzt darstellt, wäre das soetwas wie:

Für die erste:
L1: S -> a | Sa | Sb

Für die zweite:
L2: S -> a | b | Sa | Sb

per Definition eindeutig linksregulär. Die Sprache L1 lässt sich ja so beschreiben: Alle Ausdrücke, die aus mindestens einem Buchstaben bestehen (letter) und von einer beliebigen Zahlen/Buchstaben-Kombination gefolgt werden. L2 kann zusätzlich auch mit einer Zahl (digit) anfangen.

Wie schon geschrieben, wird dies in einer Programmiersprache verwendet, um Variablennamen auf Korrektheit zu überprüfen. Bei L1 dürfen diese nicht mit einer Ziffer anfangen. Bei muss mindestens ein Zeichen enthalten sein.

Beide sind (so sehe ich es zumindest) auf alle Fälle regulär (und somit Typ-3), da sich, wie bereits beschrieben ein regulärer Ausdruck finden lässt:
L1: a (a|b)*
L2: (a|b)+

 

[PlaciD]

Hallo,

dank dir. Genauso hätte ich es auch gesagt, aber die fragen gehen ja ganz klar in die andere Richtung. Evtl. Verwirrungstaktik

PlaciD

 

[Tyrell]

Wenn du da irgendwann mal eine Lösung zu hast, lass mal hören, das interessiert mich nämlich mal, wie die Aufgabe gelöst werden soll.