NFA zu Grammatik

Neue Frage »

Auf diesen Beitrag antworten »
unleashed656 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
 
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
unleashed656

Danke, das hilft mir echt weiter Daumen hoch
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »