Search Home Preferences Login Help  

2.3.4 Äquivalente Darstellung von rechtslinearen Sprachen

Äquivalenz von einseitig linearen Grammatiken zu regulären Ausdrücken (RA)

Reguläre Grammatiken
Reguläre Ausdrücke
Reguläre Sprachen

A -> a A = A -> a1 a2 ... an A

Wie sicher schon durch den Namen reguläre Sprachen angedeutet besitzt man mit regulären Ausdrücken und regulären Grammatiken ein äquivalentes Beschreibungsmittel zur Darstellung der regulären Sprachen.

Basis: G= ({S},T,P,S)
RAmit PL(G)
e{S -> e}{e}
a (für alle a in T){S -> a}{a}

Sind L1 und L2 rechtslineare Sprachen, dann sind auch
RAGmit P
L1VereinigungL2 (N1Vereinigung N2 Vereinigung {Sneu}, T,P,Sneu) P1Vereinigung P2 Vereinigung {Sneu -> S1 | S2}
L1L2 (N1VereinigungN2}, T,P,S1) P1'Vereinigung P2
P1' ist wie P1, aber jede Regel der Form A -> a wird modifiziert zu A -> aS2.
L1* (N1,T,P,S1) wie P1, aber zu jeder Regel der Form A -> a wird zusätzlich eine Regel A -> aS1 eingefügt.

1   2 Schleifenlemma

Benutzer: Gast • Besitzer: senn • Zuletzt gendert am: