endlicher Automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:50 So 28.05.2006 | | Autor: | Pollux |
| Aufgabe | Für [mm] L_n [/mm] = {a1b | b habe die Länge n-1; a,b [mm] \in \{0,1\}^\* [/mm] } , [mm] n\in \IN [/mm] zeige man folgende Aussage:
Für jedes n hat jeder determin. endl. Automat [mm] A_n [/mm] mit L( [mm] A_n) [/mm] = [mm] L_n [/mm] mindestens [mm] 2^n [/mm] Zustände
|
Hallo,
Die obige Aufgabe löst man wohl, indem man die Anzahl der Nerode-Äquivalenzklassen bzgl. der Sprache [mm] L_n [/mm] bestimmt. Dann sollte man [mm] 2^n [/mm] Äquivalenzklassen gefunden haben und damit hat der endliche Automat [mm] 2^n [/mm] Zustände. Nun hab ich aber Probleme die Äquivalenzklassen zu bestimmen. Vermutlich hängen diese von den letzten n Ziffern der Wörter aus [mm] L_n [/mm] ab. Wisst ihr welches Aussehen die einzelnen Äquivalenzklassen besitzen?
mfg
|
|
| |
|
Hallo und guten Morgen,
also es ist ja
[mm] R_n:=R(L_n)=\{ (x,y)\in\{0,1\}^{\star}|\forall z\in\{0,1\}^{\star}\:\: xz\in L_n\Leftrightarrow yz\in L_n\}
[/mm]
die zugehörige Äquivalenzrelation, und Du fragst nach der Anzahl der Äquivalenzklassen von [mm] R_n.
[/mm]
Wir beobachten zunächst, dass für alle [mm] z\in \{0,1\}^{\star} [/mm] mit [mm] |z|\geq [/mm] n und alle [mm] x,y\in\{0,1\}^{\star} [/mm] gilt:
[mm] xz\in L_n\Leftrightarrwo yz\in L_n
[/mm]
Was ist mit den [mm] |z|\leq [/mm] n-1 ? Nun, da hängt es offenbar von den Strings x,y ab, ob die Äquivalenz gilt, und zwar so:
[mm] xz\in L_n\Leftrightarrow yz\in L_n [/mm]
kann für die [mm] |z|\leq [/mm] n-1 doch nur dann gelten, wenn für [mm] j=1,\ldots [/mm] n gilt:
[mm] x_{|x|-j} [/mm] = [mm] y_{|y|-j}
[/mm]
wobei [mm] x=x_0\ldots x_{|x|-1}, y=y_0\ldots y_{|y|-1} [/mm] sei.
Damit haben wir die [mm] 2^n [/mm] Klassen gefunden:
Vertreter sind die [mm] 2^n [/mm] Strings der Länge n.
Gruss,
Mathias
|
|
|
|
