Informatiker Board | Druckvorschau: NFA zu Grammatik

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)
---- Automatentheorie (http://www.informatikerboard.de/board/board.php?boardid=13)
----- NFA zu Grammatik (http://www.informatikerboard.de/board/thread.php?threadid=2164)

Geschrieben von unleashed656 am 13.03.2015 um 12:00:

NFA zu Grammatik

Hallo, ich habe noch eine kleine frage und dachte mir ihr könntet mir da bestimmt wieder weiterhelfen. Ich habe eine Grammatik G gegeben und soll daraus einen nicht terministischen endlichen Automaten zeichnen.
G = ({0, 1}, {S, A, B}, P, S)

P = { S ::= 1S,
S ::= 0A,
A ::= 0A,
A ::= 1B,
B ::= 1B,
B ::= 1A
B ::= e }

Ich weiß nun nicht wie ich B ::= e (epsilon) zeichnen soll, oder z.b sowas wie B ::= 1.
Ich hoffe ihr könnt mir auch bei diesem Problem helfen smile

Geschrieben von Karlito am 13.03.2015 um 13:05:

Hallo unleashed656,

Bei der Grammatik handelt es sich um eine Typ-3-Grammatik oder auch rechtslineare Grammatik. D.h. alle Produktionen haben die Form:
$[latex]X \rightarrow yZ[/latex]$ oder $[latex]X \rightarrow y[/latex]$ , wobei X und Z Elemente der Menge der Nichtterminale sind und y ein Element der Terminale incl. $[latex]\varepsilon[/latex]$ ist.
Wenn also eine Produktion $[latex]X \rightarrow y[/latex]$ vorkommt, so kann es keine Weitere Produktion geben, welche daran anschließt. Im Automaten heißt das, dass in einen Terminalzustand übergegangen wird.
Wenn $[latex]X \rightarrow y [/latex]$ mit $[latex]y = \varepsilon [/latex]$ , dann reicht es im Automaten den Zustand, der X repräsentiert als Finalzustand zu deklarieren. Im Allgemeinen Fall Würde ich einen Zustand X' einführen, welcher ein Finalzustand ist und einen Übergang von X nach X' mit der Eingabe y.

Beste Grüße,

Karlito