inverser Homomorphismus -> DEA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:01 Di 11.11.2008 | | Autor: | RalU |
| Aufgabe | Hallo. Wer kann mir bei dieser Aufgabe helfen:
Sei h ein Homomorphismus von {0,1,2} nach {a,b} mit h(0)=a,h(1)=ab, h(2)=ba.
1. Bestimmen Sie h(0120) und h(21120)
2. Geben sie jeweils reguläre Ausdrücke für die Sprachen h(L(01*2)) und h(L(0 + 12)) an
3. Konstruieren Sie einen DEA, der die Sprache [mm] h^{-1}( [/mm] { ababa } ) akezeptiert.
4. wie 3. aber für die Sprache [mm] h^{-1}(L(a(ba)^{*}) [/mm] |
Also für 1. hab ich:
h(0120)=h(0)h(1)h(2)h(0)= aabbaa
und
h(21120)=h(2)h(1)h(1)h(2)h(0)=baababbaa
für 2. hab ich:
h(L(01*2))=a(ab)*
und
h(L(0+12))=a+abba
bei 3. und 4. bin ich mir nicht sicher, wie da das Vorgehen ist. Kann man direkt Homomorphismus einfach anwenden und dann einen entsprechenden DEA zeichnen?
Mein Ansatz für 3.:
Homomorphismus anwenden, dann gibt es z.b. einen gültigen Automaten mit 4 Zuständen:
[mm] A=(Q,\summe,\delta,qo,F) [/mm] mit
Q=q1 bis q4,
[mm] \summe={0,1},
[/mm]
[mm] \delta= [/mm] q0---1--->q1---1--->q2---0--->q3, Kanten zum jeweiligen Zustand selbst mit 0,2 bzw. 1,2
q0(Startzustd.)=q0
F(akzept. Zustände)=q3
Ist dieses Vorgehen richtig, oder liege ich komplett falsch?
Gruß, Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:37 Do 13.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
