NFA zu Grammatik

13.03.2015, 12:00	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


13.03.2015, 13:05	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
13.03.2015, 13:15	Auf diesen Beitrag antworten »
unleashed656	Danke, das hilft mir echt weiter

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »