Formale Sprachen: Trios (2) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 10:33 Mo 13.02.2006 | | Autor: | mathiash |
| Aufgabe | Eine verallgemeinerte sequentielle Maschine (VSM) ein Tupel
[mm] M=(Q,\Sigma,\Delta,\delta,q_0,F) [/mm] ,
wobei Q die endl. Zustandsmenge, [mm] \Sigma [/mm] das Eingabe- und [mm] \Delta [/mm] das Ausgabealphabet sind,
[mm] \delta\colon Q\times\Sigma\to P_{fin}(Q\times\Delta^{\star})= [/mm] Menge der endlichen Teilmengen von [mm] Q\times\Delta^{\star}
[/mm]
ist,
[mm] q_0 [/mm] der Anfangszustand, F die Menge der Endzustände sind.
(Interpretation von [mm] (q,x)\in\delta(p,a): [/mm] Im Zustand p bei Lesen von Zeichen a der Eingabe kann die Maschine
in Zustand q wechseln und den String x auf das Ausgabeband schreiben.
Man kann den Definitionsbereich von [mm] \delta [/mm] leicht auf [mm] Q\times\Sigma^{\star} [/mm] erweitern.
Eine VSM ist [mm] \epsilon-frei, [/mm] falls [mm] \delta\colon Q\times\Sigma\to P_{fin}(Q\times\Delta^+) [/mm] gilt.
Man definiert nun zu gegebener VSM M
[mm] M(x)=\{y\in\Delta^{\star}|\:\exists p\in F\:\:\: [\: (p.x)\in\delta (q_0,x)\:\:]\:\}
[/mm]
(fuer [mm] x\in\Sigma^{\star}) [/mm] und zu [mm] L\subseteq\Sigma^{\star}
[/mm]
[mm] M(L)=\bigcup_{x\in L}M(x),\:\: M^{-1}(x)=\{y\: |\: x\in M(y)\},\:\: M^{-1}(L)=\bigcup_{x\in L}M^{-1}(x).
[/mm]
M(L) heisst VSM-Abbildung. Falls M [mm] \epsilon-frei [/mm] ist, heisst M(L) [mm] \epsilon-freie [/mm] VSM-Abbildung.
Analog sind die Namensgebungen fuer inverse VSM-Abbildungen [mm] M^{-1}.
[/mm]
VSM-Abbildungen sind also von der Form
[mm] M\colon P(\Sigma^{\star})\to P(\Delta^{\star}),
[/mm]
inverse VSM-Abb. von der Form
[mm] M^{-1}\colon P(\Delta^{\star})\to P(\Sigma^{\star})
[/mm]
Zeige: Jedes volle Trio ist unter VSM-Abbildungen abgeschlossen. Jedes Trio ist unter
[mm] \epsilon-freien [/mm] VSM-Abbildungen abgeschlossen. |
Viel Spass, es folgen bald noch weitere Teile.
Gruss,
Mathias
|
|
|
