deterministischer endlicher automat

gegeben war folgender dea, besser gesagt die übergangstabelle,
gefragt war die reuläre grammatik die dahinter steckte

also erzeugen sie die grammatik aus der tabelle:
|0|1
-+-+-
S|E|T
E|E|E
U|E|S
T|U|V
F|E|T
V|F|E

als erstes fasse ich jeweils zu einer produktion: Anfangszustand -> Eingabezeichen Endzustand

damit komme ich auf:

S -> 0E | 1T
E -> 0E | 1E
U -> 0E | 1S
T -> 0U | 1V
F -> 0E | 1T
V -> 0F | 1E

Wie aber bestimme ich welche Nichtterminalsymbole nun Terminalsymbole erzeugen, und welche, und was ist mit möglicherweise vorkommenden epsilonregeln?

Nobuo T

Puh, ist schon ein Weilchen her... also AFAIR...
Wenn du einfach nur eine Chomsky-Grammatik angeben sollst, wuerde ich da ganz pragmatisch ran gehen.
Variablen und Alphabet kannst du einfach ablesen. Ein Startpunkt des Automaten muesste zusaetzlich gegeben sein, sonst waere er ja nicht D.
Und die regulaeren Produktionsregeln hast du auch schon.
Da auf jedes nicht-terminale Symbol in diesem Automaten immer ein beliebiges Zeichen aus dem Alphabet folgen kann (und das auch das letzte Zeichen sein kann), kannst du an die P-Regeln jeweils alternativ noch Sigma (das Alphabet, bzw. 0 oder 1) anhaengen.
Damit sollte die Sache eigentlich komplett sein.

Ein DEA ist deterministisch, d.h. es gibt keine Epsilon-Produktionen, sonst wäre es ein NEA.

Handelt es sich dabei um eine Übungsaufgabe? Also ich habe die immer gezeichnet (oder sie waren es schon) und habe den regulären Ausdruck abgelesen.
Wenn es allgemeiner sein soll, dann kannst du dir mal einen (konstruktiven) Beweis für die Äquivalenz der Menge der DEAs und der regulären Ausdrücke anschauen.

volkard

Nobuo T schrieb:

Ein Startpunkt des Automaten muesste zusaetzlich gegeben sein, sonst waere er ja nicht D.

Ich denke, dieser startet bei S und endet bei E.

Nobuo T

Waere naheliegend, aber nicht explizit angegeben.

ups vergessen...

s : start und endzustand
f : endzustand

zu der epsilonproduktion:

ich habe die musterlösung vor mir liegen:
die produktion S -> epsilon ist da verzeichnet

findest im web den bekannten Algorithmus zur Minimierung von endlichen Automaten

Suche: +DFA +Minimierung +hsg