Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Spiegelwort und Grammatik (http://www.informatikerboard.de/board/thread.php?threadid=2681)
Geschrieben von theo5 am 10.12.2015 um 20:04:
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
Geschrieben von Karlito am 10.12.2015 um 21:08:
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]](http://www.matheboard.de/latex2png/latex2png.php?<br />
S & \rightarrow &\underbrace{ aSa | bSb }_{Palindromteil (optional)} | aAb | bAa <br />
A & \rightarrow & aAa | bAb | aAb | bAa | \underbrace{\varepsilon}_{Terminierung}<br />
)
Gruß,
Karlito
Geschrieben von theo5 am 11.12.2015 um 00:26:
Danke Karlito,
damit hast du uns sehr geholfen und wir haben diese Problemstellung verstanden
.
Liebe Grüße
Forensoftware: Burning Board, entwickelt von WoltLab GmbH