Produktautomat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:52 Do 11.02.2010 | | Autor: | RalU |
| Aufgabe | Es geht um folgende Aufgabe:
Ein Alphabet [mm] \summe_ [/mm] = {a,b} ist vorgegeben.
1) DEA A1, der alle Wörter akzeptiert, die mit b anfangen
2) Produktautomat, der alle Wörter der Sprache [mm] L(A1)\cap [/mm] L(A2) akzeptiert, wobei der DEA A2 angegeben ist (siehe Dateianhang)
3) Transitionsdiagramm dieses Produktautomaten |
Nachfolgender Anhang zeigt die beiden DEA's A1 und A2:
[Dateianhang nicht öffentlich]
Der Produktautomat bezgülich Aufgabenstellung muss ja so aussehen, dass er die jenigen Wörter aktzeptiert, die sowohl DEA A1, also auch DEA A2 akzeptiert. Daher hab ich mir für den Produktautomaten folgendes Transitionsdiagramm überlegt:
[Dateianhang nicht öffentlich]
Ist dies so korrekt?
Gruß, Ralf
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
Anhang Nr. 2 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
Hallo Ralf,
zu DEA A1: q2 gehört da nicht mehr hin, also einfach nur q0 und q1, dann ist das i.O. so.
Zum Produktautomat: Da benötigst Du kein q4. So ist es falsch. Versuch es mal dahingehend zu ändern, ohne q4 auszukommen. Tipp: Orientiere dich an DEA A2.
Gruß,
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:20 Fr 12.02.2010 | | Autor: | RalU |
Warum muss ich bei DEA1 denn Q2 wegmachen? Muss man keine "Senke" einzeichnen? Was passiert denn, wenn ich in Q0 ein "a" eingebe?
Das gleiche Problem seh ich dann auch bei dem Produktautomat mit Q4.
Angenommen, ich würde hier Q4 einfach weglassen. Was passiert denn mit den Eingaben, die ich nich eingeben darf?
|
|
|
| |
|
Hallo Ralf,
> Warum muss ich bei DEA1 denn Q2 wegmachen? Muss man keine
> "Senke" einzeichnen? Was passiert denn, wenn ich in Q0 ein
> "a" eingebe?
Dann wird die Eingabe nicht akzeptiert und es gibt keine Ausgabe.
So wie es sein soll.
> Das gleiche Problem seh ich dann auch bei dem
> Produktautomat mit Q4.
> Angenommen, ich würde hier Q4 einfach weglassen. Was
> passiert denn mit den Eingaben, die ich nich eingeben darf?
Sie werden nicht akzeptiert. BTW, so oder so ist der Produktautomat falsch, er würde nämlich beispielsweise nie das Wort bbabaa akzeptieren, obwohl es definitiv ein korrektes Wort wäre.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:11 So 14.02.2010 | | Autor: | felixf |
Hallo Anna,
> zu DEA A1: q2 gehört da nicht mehr hin, also einfach nur
> q0 und q1, dann ist das i.O. so.
das sehe ich anders. Ich wuerde hier keinesfalls auf q2 verzichten.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:40 Mo 15.02.2010 | | Autor: | RalU |
>
> > zu DEA A1: q2 gehört da nicht mehr hin, also einfach nur
> > q0 und q1, dann ist das i.O. so.
>
> das sehe ich anders. Ich wuerde hier keinesfalls auf q2
> verzichten.
>
> LG Felix
>
Das sehe ich auch so.
Ein DEA ist ja als 5-Tupel definiert DEA [mm] A=_{def}(Q,\summe_ ,\delta, q_{0},F) [/mm] wobei
Q= die Menge der Zustände,
[mm] \summe_ [/mm] das Eingabealphapbet,
[mm] \delta [/mm] die Überführungsfunktion, die als eine totale Funktion definiert (also keine "Lücken" hat) ist und somit jedem einzelnen Zustand aus Q immer jedes Zeichen aus dem Eingabealphabet zugewiesen werden muss (in Form von Transitionen) (man kann [mm] \delta [/mm] dann in Form einer Tabelle oder Transitionsdiagramms angeben),
F=Menge der akzeptierenden Zustände
und [mm] q_{0} [/mm] der Startzustand.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:52 Mo 15.02.2010 | | Autor: | Anna-Lyse |
Hallo Ralf,
ja sorry, ich hatte DEA nicht berücksichtigt.
Gruß,
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:52 Mo 15.02.2010 | | Autor: | Anna-Lyse |
Hallo Felix,
> > zu DEA A1: q2 gehört da nicht mehr hin, also einfach nur
> > q0 und q1, dann ist das i.O. so.
>
> das sehe ich anders. Ich wuerde hier keinesfalls auf q2
> verzichten.
Stimmt, es ging ja um DEA.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:00 So 14.02.2010 | | Autor: | RalU |
Ich hab mal noch ne andere Lösung für den Produktautomat, der L(A1) [mm] \cap [/mm] L(A2)akzeptieren soll(siehe Anhang). Wie siehts denn damit aus?
[Dateianhang nicht öffentlich]
Gruß, Ralf
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:19 So 14.02.2010 | | Autor: | felixf |
Hallo Ralf,
> Ich hab mal noch ne andere Lösung für den Produktautomat,
> der L(A1) [mm]\cap[/mm] L(A2)akzeptieren soll(siehe Anhang). Wie
> siehts denn damit aus?
>
> [Dateianhang nicht öffentlich]
der Automat ist nichtmals deterministisch.
Er akzeptiert keine inkorrekten Woerter, jedoch gibt es bei korrekten Woertern sowohl Durchlaufmoeglichkeiten, die zum Zielzustand fuehren, wie auch Durchlaufmoeglichkeiten, die nicht zum Zielzustand fuehren.
Da man hier auch ohne viel Aufwand einen deterministischen Automaten angeben kann, wuerde ich eher so einen angeben.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:26 Mo 15.02.2010 | | Autor: | RalU |
> Hallo Ralf,
>
> > Ich hab mal noch ne andere Lösung für den Produktautomat,
> > der L(A1) [mm]\cap[/mm] L(A2)akzeptieren soll(siehe Anhang). Wie
> > siehts denn damit aus?
> >
> > [Dateianhang nicht öffentlich]
>
> der Automat ist nichtmals deterministisch.
>
> Er akzeptiert keine inkorrekten Woerter, jedoch gibt es bei
> korrekten Woertern sowohl Durchlaufmoeglichkeiten, die zum
> Zielzustand fuehren, wie auch Durchlaufmoeglichkeiten, die
> nicht zum Zielzustand fuehren.
>
> Da man hier auch ohne viel Aufwand einen deterministischen
> Automaten angeben kann, wuerde ich eher so einen angeben.
>
> LG Felix
>
Ja, ich hab den Nichtdeterminismus nun auch bemerkt. Die Transition q1'' mit a zu sich selbst stört. Allerdings weiß ich dann nicht, wie z.B. das wort w=babaa akzeptieren kann...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:36 Mo 15.02.2010 | | Autor: | felixf |
Moin!
> Ja, ich hab den Nichtdeterminismus nun auch bemerkt. Die
> Transition q1'' mit a zu sich selbst stört.
Genau, die muss weg.
> Allerdings
> weiß ich dann nicht, wie z.B. das wort w=babaa akzeptieren
> kann...
Von q2'' musst du bei einem b nicht zu q4, sondern zu q1'' springen. Dann funktioniert es.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:58 Mo 15.02.2010 | | Autor: | RalU |
> Von q2'' musst du bei einem b nicht zu q4, sondern zu q1''
> springen. Dann funktioniert es.
>
> LG Felix
>
Vielen Dank für deine Hilfe! Ich denke du hast Recht.
Im Prinzip is es ja einfach nur eine "Hintereinanderschaltung" der beiden Ausgangs-DEA's.
Und wenn jetzt die Bedingung zur Konstruktion nicht L(A) [mm] \cap [/mm] L(B) sondern z.B. L(A) [mm] \cup [/mm] L(B) lauten würde, dann würde mein Produktautomat doch so aussehen:
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:23 Mo 15.02.2010 | | Autor: | felixf |
Hallo!
> Vielen Dank für deine Hilfe! Ich denke du hast Recht.
> Im Prinzip is es ja einfach nur eine
> "Hintereinanderschaltung" der beiden Ausgangs-DEAs.
Genau. (Und lass den Apostroph da lieber weg :) )
> Und wenn jetzt die Bedingung zur Konstruktion nicht L(A)
> [mm]\cap[/mm] L(B) sondern z.B. L(A) [mm]\cup[/mm] L(B) lauten würde, dann
> würde mein Produktautomat doch so aussehen:
>
> [Dateianhang nicht öffentlich]
Genau. Ich wuerd das allerdings nicht als Produktautomaten bezeichnen :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:14 So 14.02.2010 | | Autor: | felixf |
Hallo Ralf,
> Es geht um folgende Aufgabe:
> Ein Alphabet [mm]\summe_[/mm] = {a,b} ist vorgegeben.
> 1) DEA A1, der alle Wörter akzeptiert, die mit b
> anfangen
> 2) Produktautomat, der alle Wörter der Sprache [mm]L(A1)\cap[/mm]
> L(A2) akzeptiert, wobei der DEA A2 angegeben ist (siehe
> Dateianhang)
ist hier nach irgendeinem Automaten gefragt, der $L(A1) [mm] \cap [/mm] L(A2)$ akzeptiert, oder nach dem Produktautomaten von A1 und A2?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:28 Mo 15.02.2010 | | Autor: | RalU |
> Hallo Ralf,
>
> > Es geht um folgende Aufgabe:
> > Ein Alphabet [mm]\summe_[/mm] = {a,b} ist vorgegeben.
> > 1) DEA A1, der alle Wörter akzeptiert, die mit b
> > anfangen
> > 2) Produktautomat, der alle Wörter der Sprache
> [mm]L(A1)\cap[/mm]
> > L(A2) akzeptiert, wobei der DEA A2 angegeben ist (siehe
> > Dateianhang)
>
> ist hier nach irgendeinem Automaten gefragt, der [mm]L(A1) \cap L(A2)[/mm]
> akzeptiert, oder nach dem Produktautomaten von A1 und A2?
>
> LG Felix
>
Der genaue Wortlaut lautet: Geben Sie einen Produktautomaten A vom Typ DEA an, der L(A1) [mm] \cap [/mm] L(A2) akzeptiert und zeichnen sie das Transitionsdiagramm.
|
|
|
|
