Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » DFA bzw. DEA Automat

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

DFA bzw. DEA Automat

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

DFA bzw. DEA Automat

Zitatantwort auf diesen Beitrag erstellen

HAllo,
sitze vor meiner ersten Übungsaufgabe und bin ratlos traurig

vielleicht könnt ihr mir ja auf die Sprünge helfen:

Sei A die Menge aller Wörter aus {a,b}^* mit gerader Länge,
die mit einem a anfangen und auf b enden.

a)Geben sie eine DFA an, der A entscheidet.

b)Geben sie einen regulären Ausdruck an, der A beschreibt.

Zu a)
Soll der DFA entscheiden können ob ein Wort am Anfang a und am Ende b besitzt? falls ja dann entscidet der DFA A?,bin mir auch nicht sicher wie ich das zunächst rein Formal schreiben kann.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Pampelmuse: 12.04.2007 17:18.

12.04.2007 16:31

Nehmen Sie Pampelmuse in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Der DFA soll die Sprache A entscheiden. Das bedeutet, dass dein DFA angesetzt auf ein Wort aus A in einem akzeptierenden Zustand endet und angesetzt auf ein Wort, welches nicht in A liegt in einem nicht-akzeptierenden Zustand endet.

Du musst nun genau einen DFA konstruieren, der nur Wörter akzeptiert (d.h. in einem akzeptierenden Zustand endet), die

1) mit a beginnen
2) mit b enden
3) gerade Wortlänge haben

Da du offensichtlich garncith weißt, wie der Hase läuft gebe ich dir mal einen möglichen regulären Ausdruck an (der hoffentlich richtig ist):

$[latex]a\big((a+b)(a+b)\big)^\ast b[/latex]$
Jedes Wort beginnt mit a und endet mit b. Dazwischen kann man optional noch was einfügen. Aber immer nur im Zweierpack damit das Wort gerade Länge hat.

12.04.2007 23:04

Nehmen Sie Tobias in Ihre Freundesliste auf

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Hil,
erst mal Danke für den Beitrag
Das + ist mir neu weiß nicht was es bedeutet, für mich wirkt das so das nur Wörter der Form:
a abab b, a abababab b
und nicht
a ab b bzw. a aa bb b

Wie läüft den der Hase denn?,ist es möglich dies auch zeichnerisch zu lösen bzw. in der Form
A-->aB
...
?

13.04.2007 08:37

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Also die Definition die du gegeben hast lässt keinen Raum für Spekulation:

Zitat:

Sei A die Menge aller Wörter aus {a,b}^* mit gerader Länge,
die mit einem a anfangen und auf b enden.

aaabbb hat gerade Länge (6), beginnt mit einem a und endet mit einem b. Also ist es ein Wort der Sprache A.

Weißt du überhaupt, was ein regulärer Ausdruck ist? Das "+" steht für "oder". Also bei dem Ausdruck (a + b) kannst du entweder ein a oder ein b wählen.

Was du mit "zeichnerisch" meinst ist mir ein Rätsel. Du sollst einen Automaten konstruieren.

13.04.2007 10:12

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Ok, hab den Hase gefunden:
Dein regulären Ausdruck hab ich nix entgegenzusetzen
hatte dies gefunden was völlig gleich ist:
a(a+ab+ba+b)*

Zum Zeichnerischen :
Also meines wissensläßt sich
für die Teilaufgabe a) entweder eine Zeichnerische Lösung erstellen
oder auch so eine Aufgebaute Lösung A--> ... erstellen.

Pampelmuse hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Pampelmuse: 13.04.2007 16:15.

13.04.2007 15:15

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Dein Automat ist falsch denn es wird das Wort aab akzeptiert, das nicht gerade Länge hat.

Dein regulärer Ausdruck a(a+ab+ba+b)* ist ebenfalls falsch. Die Wörter enden nicht auf b und die gerade Länge hast du nicht beachtet.

13.04.2007 16:58

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

stimmt

Neuer Versuch

Pampelmuse hat dieses Bild (verkleinerte Version) angehängt:

13.04.2007 17:48

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Jawollski. Jetzt noch den akzeptierenden Zustand markieren und dann schauts gut aus.

13.04.2007 18:13

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Achso endzustand z_4 umkreisen ,
besten Dank nochmal.

14.04.2007 10:14

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » DFA bzw. DEA Automat