Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Kontextfreie Grammatik bestimmen und umwandeln in Kellerautomat
Guten Abend,
so, das werden meine letzten Heldentaten vor der Klausur sein. Vielleicht hat ja noch jemand Lust, sie abzugleichen, zu verpflücken oder zu verbessern. Los geht’s:
Mir ist klar, dass ich dafür bspw. das Pumplemma nutzen kann, finde für diese Sprache aber gerade keine Lösung.
[m]G = ({S,K,L,M,N,Z},{j,a,!},S,P) mit den Produktionsregeln P:
S → XKYNnZ
X → j
Y → KYN | Y‛
K → k
Y‛→ L!Y‛M[/m] *
[m]L → !
M → a | ɛ
N → n
Z → ![/m]
*Die einzige Möglichkeit, die ich sehe, um dafür zu sorgen, dass l≠m gilt, ist, ein a fest einzufügen in diese Ableitungsregel, wodurch es auf jeden Fall ein ! mehr geben wird als a’s. Die M-Variablen sind darüber hinaus beliebig ableitbar als a oder ɛ.
Ist das zulässig? Es ist womöglich nicht elegant, aber eine bessere Lösung fällt mir gerade nicht ein - würden mich aber interessieren!
[m]M(L) = ({Z},{a,!,j,ɛ},{S,X,Y,M,M‛,N,a,!,j,ɛ},ð,Z,S,{∅}) mit ð:
ɛ;S →XKYNnZ
ɛ;X →j
ɛ;Y →KYN
ɛ;Y →Y‛
ɛ;K →k
ɛ;Y‛→LY‛Ma
ɛ;L →!
ɛ;M →a
ɛ;M →ɛ
ɛ;N →n
ɛ;Z →!
j;j →ɛ
a;a →ɛ
!;! →ɛ[/m]
[m]
G = ({S,X,Y,M,M‛,N},{a,!,j},S,P) mit den Produktionsregeln P:
S → MXN
X → MXN | Y | ɛ
Y → !a
M → M‛M‛
M‛→ a
N → j[/m]
[m]M(L) = ({Z},{a,!,j,ɛ},{S,X,Y,M,M‛,N,a,!,j,ɛ},ð,Z,S,{∅}) mit ð:
ɛ;S →MXN
ɛ;X →MXN
ɛ;X →Y
ɛ;X →ɛ
ɛ;Y →!a
ɛ;M →M‛M‛
ɛ;M‛→a
ɛ;N →j
a;a →ɛ
!;! →ɛ
j;j →ɛ[/m]
LG Forumsnutzer