 NFA zu Grammatik |
unleashed656
Grünschnabel
Dabei seit: 12.03.2015
Beiträge: 7
 |
|
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 
|
|
13.03.2015 12:00 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?X \rightarrow yZ) oder ![[latex]X \rightarrow y[/latex]](http://www.matheboard.de/latex2png/latex2png.php?X \rightarrow y) , wobei X und Z Elemente der Menge der Nichtterminale sind und y ein Element der Terminale incl. ![[latex]\varepsilon[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\varepsilon) ist.
Wenn also eine Produktion 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]](http://www.matheboard.de/latex2png/latex2png.php?X \rightarrow y ) mit ![[latex]y = \varepsilon [/latex]](http://www.matheboard.de/latex2png/latex2png.php?y = \varepsilon ) , 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
|
|
|
13.03.2015 13:05 |
|
|
unleashed656
Grünschnabel
Dabei seit: 12.03.2015
Beiträge: 7
|
|
Danke, das hilft mir echt weiter 
|
|
|
13.03.2015 13:15 |
|
|
|
