Informatiker Board | Druckvorschau: Reguläre Grammatik aus DEA

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)
--- Reguläre Grammatik aus DEA (http://www.informatikerboard.de/board/thread.php?threadid=2522)

Geschrieben von GAFO am 31.10.2015 um 17:48:

Reguläre Grammatik aus DEA

Hallo Zusammen,
ich sitze schon über eine Stunde an dieser Aufgabe:

i.imgur.com/UcX4Ci5.jpg [BIL_URL]

und ich verstehe zwar den Zusammenbau des Wortes, aber
nicht wie ich daraus eine Grammatik schreibe. In diesem Fall liegt es am C
was in der unteren Schleifen 0-n mal vorkommen kann, aber oben mindestens einmal und danach beliebig oft ..

C->c | e | cC etc
aber das zu kombinieren ist mir ein Rätsel

Vielleicht könnte mir jemand daraus eine reg Grammatik schreiben und kurz erklären wie man darauf kommt smile

,lg GAFO

soweit meine Theorie: (E entpsricht dem Summen-Zeichen)

{a,b,c}^+ ° {c}* ° {a} ° E*\{c} ° {c} ° {c}* = P1
{a,b,c}^+ ° {c}* ° {b} ° {c}* = P2

und dann

P1 ° {a} ° {P1 oder P2}*
P2 ° {a} ° {P1 oder P2}*

etc etc etc

bis Jetzt bin ich bei:

S->LCARCS | LCBCS

L->a|b|c
A->a
B->b
R-> a|b|aR|bR|µ

aber ich hab ein Brett vorm Kopf verwirrt

Geschrieben von Karlito am 31.10.2015 um 18:42:

Hallo GAFO,

mach es dir nicht so kompliziert. Du musst im Prinzip nur ablesen. Jeder Zustand wird zu einem Nichtterminal auf der linken Seite der Produktion und jeder Übergang zu einem Terminal gefolgt von dem Nichtterminal welcher dem Folgezustand entspricht. Zusätzlich wird bei einem Finalzustand eine Produktion nach $[latex]\mu[/latex]$ eingeführt.

Für die ersten Zustände heißt das:

$[latex]<br /> Q_0 & \rightarrow & aQ_2 | bQ_2 | cQ_2 | \mu<br /> Q_2 & \rightarrow & aQ_1 | bQ_3 | cQ_2 <br /> & \dots &<br /> [/latex]$

Gruß,

Karlito