Zusätzlicher Zustand beim DEA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben sei ein beliebiger NEA [mm] $M=(Z,\Sigma,\delta,\{z_{0}\},E)$ [/mm] mit einem einzigen Anfangszustand [mm] $z_{0}$ [/mm] sowie der Eigenschaft, dass [mm] $|\delta(z,a)| \le [/mm] 1$ für alle $z [mm] \in [/mm] Z$ und $a [mm] \in \Sigma$ [/mm] gilt. Das heißt, für jeden Zustand und jedes Zeichen gibt es höchstens einen Nachfolgezustand, es könnte aber auch keinen Nachfolgezustand geben.
Wie kann man aus M einen DEA konstruieren, der nur einen Zustand mehr hat als M und der die gleiche Sprache wie M akzeptiert? Geben Sie eine formale Definition dieses Automaten an. |
Hallo,
diverse Automaten-Aufgaben, die nach "Schema F" zu lösen sind, haben mir keine Probleme bereitet, bei der hier muss ich leider passen. Ich versuche krampfhaft, das "Schema F" aus der Wikipedia ![[]](/images/popup.gif) Potenzmengenkonstruktion Beispiele irgendwie anzuwenden, bleibe aber hängen, da es bis auf [mm] $z_{0}$ [/mm] keine Zustände gibt.
Ich habe mir gedacht, man könnte hier beim DEA das [mm] $\Sigma'$ [/mm] um z.B. x und das Z' um den Zustand Y erweitern. Damit würde auch weiterhin die gleiche Sprache akzeptiert werden, wie vom NEA.
Kann das stimmen?/Weiß jemand eine bessere Idee?
Auf jeden Fall vielen Dank!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:41 Sa 14.05.2011 | | Autor: | felixf |
Moin!
> Gegeben sei ein beliebiger NEA
> [mm]M=(Z,\Sigma,\delta,\{z_{0}\},E)[/mm] mit einem einzigen
> Anfangszustand [mm]z_{0}[/mm] sowie der Eigenschaft, dass
> [mm]|\delta(z,a)| \le 1[/mm] für alle [mm]z \in Z[/mm] und [mm]a \in \Sigma[/mm]
> gilt. Das heißt, für jeden Zustand und jedes Zeichen gibt
> es höchstens einen Nachfolgezustand, es könnte aber auch
> keinen Nachfolgezustand geben.
Koennen eure NEAs [mm] $\varepsilon$-Transitionen [/mm] haben? Ich gehe mal davon aus, dass dies nicht der Fall ist.
In dem Fall ist so ein NEA doch schon fast ein DEA: der einzige Unterschied ist, dass nicht fuer jeden Zustand und jede Eingabe umbedingt ein Nachfolgezustand definiert ist. Sprich, du musst nur einen zusaetzlichen Zustand einfuegen, sozusagen einen "Es ist was schiefgelaufen, egal was kommt, das Wort wird nie akzeptiert"-Zustand.
LG Felix
|
|
|
| |
|
| Aufgabe | Gegeben sei ein beliebiger NEA $ [mm] M=(Z,\Sigma,\delta,\{z_{0}\},E) [/mm] $ mit einem einzigen Anfangszustand $ [mm] z_{0} [/mm] $ sowie der Eigenschaft, dass $ [mm] |\delta(z,a)| \le [/mm] 1 $ für alle $ z [mm] \in [/mm] Z $ und $ a [mm] \in \Sigma [/mm] $ gilt. Das heißt, für jeden Zustand und jedes Zeichen gibt es höchstens einen Nachfolgezustand, es könnte aber auch keinen Nachfolgezustand geben.
Wie kann man aus M einen DEA konstruieren, der nur einen Zustand mehr hat als M und der die gleiche Sprache wie M akzeptiert? Geben Sie eine formale Definition dieses Automaten an. |
Hi Felix,
> Koennen eure NEAs [mm]\varepsilon[/mm]-Transitionen haben? Ich gehe
> mal davon aus, dass dies nicht der Fall ist.
Epsilon-Transitionen wurden in der Vorlesung nicht definiert.
> In dem Fall ist so ein NEA doch schon fast ein DEA: der
> einzige Unterschied ist, dass nicht fuer jeden Zustand und
> jede Eingabe umbedingt ein Nachfolgezustand definiert ist.
> Sprich, du musst nur einen zusaetzlichen Zustand einfuegen,
> sozusagen einen "Es ist was schiefgelaufen, egal was kommt,
> das Wort wird nie akzeptiert"-Zustand.
Auch das wurde in der Vorlesung nicht eingeführt, aber Google hat mich auf den Begriff "Fangzustand" gebracht. Ich denke mal, dass Du das gemeint hast...
Es ist zwar nicht die feine Art, aber kann man nicht die Folie links oben auf Seite 3 als Lösung verwenden?
Link-Text
> LG Felix
Echt ein großes Danke an der Stelle! Ich hätte nicht gedacht, dass ich in theoretischer Informatik hier so schnell eine Antwort erhalten würde (einfach weil dieses Fachgebiet abschreckend und exotisch ist). 
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:09 Sa 14.05.2011 | | Autor: | felixf |
Moin el_grecco!
> Gegeben sei ein beliebiger NEA
> [mm]M=(Z,\Sigma,\delta,\{z_{0}\},E)[/mm] mit einem einzigen
> Anfangszustand [mm]z_{0}[/mm] sowie der Eigenschaft, dass
> [mm]|\delta(z,a)| \le 1[/mm] für alle [mm]z \in Z[/mm] und [mm]a \in \Sigma[/mm]
> gilt. Das heißt, für jeden Zustand und jedes Zeichen gibt
> es höchstens einen Nachfolgezustand, es könnte aber auch
> keinen Nachfolgezustand geben.
>
> Wie kann man aus M einen DEA konstruieren, der nur einen
> Zustand mehr hat als M und der die gleiche Sprache wie M
> akzeptiert? Geben Sie eine formale Definition dieses
> Automaten an.
>
> > Koennen eure NEAs [mm]\varepsilon[/mm]-Transitionen haben? Ich gehe
> > mal davon aus, dass dies nicht der Fall ist.
>
> Epsilon-Transitionen wurden in der Vorlesung nicht
> definiert.
Ah, gut. Die kann man zwar loswerden, aber dann werden die Uebergangsmengen teilweise groesser. Insofern ist es gut so etwas nicht zu haben 
> > In dem Fall ist so ein NEA doch schon fast ein DEA: der
> > einzige Unterschied ist, dass nicht fuer jeden Zustand und
> > jede Eingabe umbedingt ein Nachfolgezustand definiert ist.
> > Sprich, du musst nur einen zusaetzlichen Zustand einfuegen,
> > sozusagen einen "Es ist was schiefgelaufen, egal was kommt,
> > das Wort wird nie akzeptiert"-Zustand.
>
> Auch das wurde in der Vorlesung nicht eingeführt, aber
> Google hat mich auf den Begriff "Fangzustand" gebracht. Ich
> denke mal, dass Du das gemeint hast...
Ja, so kann man das nennen Ich weiss nicht ob es einen festen Namen dafuer gibt.
> Es ist zwar nicht die feine Art, aber kann man nicht die
> Folie links oben auf Seite 3 als Lösung verwenden?
>
> Link-Text
Ja, kann man Eventuell muss man um es formal korrekt aufzuschreiben noch ein paar Dinge hin- und herdefinieren, je nachdem wie eure Definitionen von NEA und DEA nun genau aussehen...
> Echt ein großes Danke an der Stelle! Ich hätte nicht
> gedacht, dass ich in theoretischer Informatik hier so
> schnell eine Antwort erhalten würde (einfach weil dieses
> Fachgebiet abschreckend und exotisch ist).
Die Theoretische Informatik war der Teil der Informatik der mir im Studium am meisten Spass gemacht hat Ist halt recht mathematisch...
LG Felix
|
|
|
|
