Herleiten eines DEA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | http://www.ling.uni-potsdam.de/~kolb/ECL/ECL-Aufgabensammlung-2012-2.pdf |
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://entwickler-forum.de/showthread.php/74030-Herleiten-eines-endlichen-Automaten?p=278214#post278214
(Leider keine Antwort bisher)
Hallo!
In dem Link oben ist die Lösung der ersten Aufgabe 2-0 das Diagramm eines endlichen Automaten. Mir geht es nun darum, die einzelnen Bestandteile dieses Automaten auszumachen:
Ein DEA ist ja (Σ, S, s0, δ, F):
Jetzt geht es mir darum, zu verstehen, was hier die einzelnen Bestandteile sind. Ich sehe das folgendermaßen:
Σ = {ε, hör, auf, ge, zu, t, en}
s0 = Ist im Diagramm die 1, aber der Anfangszustand besteht ja nicht aus elnem Element des Alphabets, oder? Also ist s0 hier nicht weiter definiert?
F = {hören, gehört, zuhören, aufhören, aufzuhören, zuzuhören, hört, zuhört, aufhört, aufgehört, zugehört}, war ja schon vorgegeben
S = Zustandmenge: Sind das hier alle theoretisch möglichen Kombinationen aus den Elementen des Alphabets + Anfangszustand 1? Oder nur die Zustände 1 bis 12, die im Diagramm gezeigt sind?
δ = ist nicht total, weil es ja Zustände gibt, die nicht definiert sind. Delta ist z. B. δ(1,ε) = 2, δ(2,hör) = 3, δ(3,zu) gibts z. B. nicht, δ(3,en) = 4 usw., also für jeden Zustand Angaben: (Ausgangszustand,Eingab) = Endzustand
Geht das halbwegs in die richtige Richtung?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:23 Sa 16.08.2014 | | Autor: | felixf |
Moin!
> http://www.ling.uni-potsdam.de/~kolb/ECL/ECL-Aufgabensammlung-2012-2.pdf
>
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
>
> http://entwickler-forum.de/showthread.php/74030-Herleiten-eines-endlichen-Automaten?p=278214#post278214
> (Leider keine Antwort bisher)
>
>
>
> Hallo!
>
> In dem Link oben ist die Lösung der ersten Aufgabe 2-0 das
> Diagramm eines endlichen Automaten. Mir geht es nun darum,
> die einzelnen Bestandteile dieses Automaten auszumachen:
>
> Ein DEA ist ja (Σ, S, s0, δ, F):
Genau.
> Jetzt geht es mir darum, zu verstehen, was hier die
> einzelnen Bestandteile sind. Ich sehe das folgendermaßen:
> Σ = {ε, hör, auf, ge, zu, t, en}
Genau.
> s0 = Ist im Diagramm die 1, aber der Anfangszustand besteht
> ja nicht aus elnem Element des Alphabets, oder? Also ist s0
> hier nicht weiter definiert?
Bevor du mit $s0$ anfaengst, solltest du dir klarmachen, was $S$ ist. Schliesslich ist $s0$ ein Element aus $S$. Und ja, hier ist $s0 = 1$.
> F = {hören, gehört, zuhören, aufhören, aufzuhören,
> zuzuhören, hört, zuhört, aufhört, aufgehört,
> zugehört}, war ja schon vorgegeben
Ich weiss ja nicht was $F$ bei euch ist. Normalerweise ist das die Menge der Zielzustaende. Das waere hier [mm] $\{ 4, 5, 8, 12 \}$.
[/mm]
> S = Zustandmenge: Sind das hier alle theoretisch möglichen
> Kombinationen aus den Elementen des Alphabets +
> Anfangszustand 1? Oder nur die Zustände 1 bis 12, die im
> Diagramm gezeigt sind?
Das sind die Zustaende 1 bis 12 aus dem Diagramm. Der Automat ist ja immer in einem dieser Zustaende.
> δ = ist nicht total, weil es ja Zustände gibt, die nicht
> definiert sind. Delta ist z. B. δ(1,ε) = 2, δ(2,hör) =
> 3, δ(3,zu) gibts z. B. nicht, δ(3,en) = 4 usw., also für
> jeden Zustand Angaben: (Ausgangszustand,Eingab) =
> Endzustand
Genau.
Du kannst das zu einer totalen Funktion erweitern, indem du einen weiteren Zustand 13 hinzufuegst, zu den alle nicht definierten Zustandsuebergaenge hingehen und von dem aus man nicht wieder wegkommt. Dieser Zustand gehoert nicht in die Menge $F$.
LG Felix
|
|
|
| |
|
Sorry für die späte Rückmeldung! Vielen Dank! Hat mir sehr geholfen!
|
|
|
|
