Spiegelwort und Grammatik

Neue Frage »

Auf diesen Beitrag antworten »
theo5 Spiegelwort und Grammatik

Hallo,

wir haben mehrere Aufgaben zu Grammatiken bekommen, wobei wir eine Aufgabe nicht lösen können. Folgende Sprache sei gegeben:

L = {cd | c,d in {a,b}*, |c| = |d|, c ungleich d^R}

Hierzu sollen wir nun die Grammatik angeben, also auch Produktionsregeln, die jeweilige Startvariable usw.

Wir wissen hier nur nicht weiter und hoffen auf Hilfestellungen.

Liebe Grüße
 
Auf diesen Beitrag antworten »
Karlito

Hallo theo5,

Es muss sicher gestellt werden, dass das Palindrom an irgendeiner Stelle unterbrochen wird. Nur dann darf die Ableitung terminieren.

[latex]<br />
S & \rightarrow &\underbrace{ aSa | bSb }_{Palindromteil (optional)} | aAb | bAa <br />
A & \rightarrow & aAa | bAb | aAb | bAa | \underbrace{\varepsilon}_{Terminierung}<br />
[/latex]

Gruß,

Karlito
Auf diesen Beitrag antworten »
theo5

Danke Karlito,

damit hast du uns sehr geholfen und wir haben diese Problemstellung verstanden smile .

Liebe Grüße
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »