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)
----- Reguläre Grammatik erzeugen (http://www.informatikerboard.de/board/thread.php?threadid=1252)
Geschrieben von Spender am 21.07.2012 um 14:43:
Reguläre Grammatik erzeugen
So noch eine.
Eine reguläre Grammatik, die die Sprache L erzeugt
L={a(bc)^nd|n>=0}
Wie fang ich da grundlegend an? Wie viele Platzhaltervariablen brauche ich und wonach wird ersetzt bzw. abgeleitet?
Es dankt
der SPender
Geschrieben von Karlito am 24.07.2012 um 11:13:
Ich löse das Beispiel mal, weil mir gerade langweilig ist.
Als erstes habe ich einen Automaten erstellt, welcher der Grammatik entspricht. Dieses Beispiel hier ist so günstig, dass man sofort die Grammatik ablesen kann. Der Automat ist im Anhang zu finden. Die Produktionen lassen sich direkt ablesen. Der Finalzustand hat eine Epsilon-Produktion.
![[latex]G = \{\{S,A,B,C,D,a,b,c,d\}, \{a,b,c,d\}, P, \{S\}\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?G = \{\{S,A,B,C,D,a,b,c,d\}, \{a,b,c,d\}, P, \{S\}\})
mit
![[latex] \begin{array}{rcl}<br />
P = \{ S & \rightarrow & aA, <br />
A & \rightarrow & bB, <br />
B & \rightarrow & cC, <br />
C & \rightarrow & dD, <br />
D & \rightarrow &cC, <br />
D & \rightarrow & \epsilon \}<br />
\end{array}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php? \begin{array}{rcl}<br />
P = \{ S & \rightarrow & aA, <br />
A & \rightarrow & bB, <br />
B & \rightarrow & cC, <br />
C & \rightarrow & dD, <br />
D & \rightarrow &cC, <br />
D & \rightarrow & \epsilon \}<br />
\end{array}<br />
)
Forensoftware: Burning Board, entwickelt von WoltLab GmbH