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:
oder , wobei X und Z Elemente der Menge der Nichtterminale sind und y ein Element der Terminale incl. 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 mit , 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 |
|
|
|