Deterministischer Automat der eine gerade Anzahl von a's und multiple von 3 b's akzeptiert

Hallo,

ich moechte einen Automaten konstruieren der eine gerade Anzahl von a's und multiple-von-3 b's akzeptiert. Wie macht man sowas?　Ich habe schon zwei Automaten konstuiert, der eine akzeptiert eine gerade Anzahl von a's und der andere vielfache von 3　b's. Aber bei der Konstruktion von einem Automaten der beides akzepiert funktioniert am Ende gar nichts mehr.

mfg

volkard

Peter_Pan91 schrieb:

Ich habe schon zwei Automaten konstuiert, der eine akzeptiert eine gerade Anzahl von a's

Ich möchte den Startknoten S nennen und den anderen A.

Peter_Pan91 schrieb:

und der andere vielfache von 3　b's.

Ich möchte den Startknoten S nennen und den anderen B und den dritten BB.

Ich hoffe, wir stellen uns jetzt dieselben Automaten vor.

Mit dieser Bebbennung kam ich weiter. Ich baue die Knoten

S           A

B           AB

BB          ABB

und die Kanten sind dann glaube ich klar.

Hallo,

sorry habe im ersten Post Informationen unterschlagen,
der erste Automat soll das akzeptieren:
{w element von {a, b}* | w enthaelt eine gerade Anzahl von a's}

und der zweite:
{w element von {a, b}* | w enthaelt multiple von 3 b's}.

und der dritte dann sozusagen das:

{w element von {a, b}* | w enthaelt eine gerade Anzahl von a's und multiple von 3 b's}.

volkard

Doch, so hatte ich das verstanden. Ich denke, es liegt kein Mißverständnis vor.

S           A 

B           AB 

BB          ABB

a-Kanten:
S A
A S
B AB
AB B
BB ABB
ABB BB

b-Kanten:
S B
B BB
BB S
A AB
AB ABB
ABB A

Start-Zustand ist S

akzeptierende Zustände:
nur S

So können die a horizontal spielen und die b vertika und sie kommen sich nicht isn Gehege. Genau dann, wenn die Zahl der a durch 2 teilbar ist, befindet sich der Automat in einem, Zustand der linken Spalte (S B BB). Genau dann, wenn die Zahl der b durch 3 teilbar ist, befindet sich der Automat in der obren Zeile (S A).
Genau dann, wenn beides zutrifft, befindet er sich im Zustand S.

Hallo,

habe es mir jetzt mal aufgemalt und funktioniert super, gibt es einen Weg nach dem man da vorgehen kann wenn man einen solchen Automaten konstruieren soll und schon zwei Automaten hat?

volkard

Peter_Pan91 schrieb:

Hallo,
habe es mir jetzt mal aufgemalt und funktioniert super, gibt es einen Weg nach dem man da vorgehen kann wenn man einen solchen Automaten konstruieren soll und schon zwei Automaten hat?

Kann ich mir nicht vorstellen.
Aber ich habe nicht die beiden alten kombiniert. Ich habe nur die verschiedenen interessanten Möglichkeiten, wieviele a und b bisher gelesen wurden, gesammelt, und die Kanten dazwischengemalt. Daß das dann hübsch wurde, ist reiner Zufall. Ich hätte mich auch durchgequält, wenn es unübersichtlich geworden wäre.

otze

Naja, das was Volkard gemacht hat, ist in etwa schon das, was ich machen würde:

Nimm deine beiden Automaten mit jeweiligen Zuständen A={a1,a2,a3...} und B={b1,b2,b3,...}.

Bilde das karthesische Produkt AxB={(a1,b1),...} der Zustände. Jeder so erhaltene Zustand ist ein Zustand des end-automaten. Endzustände sind die Zustände (a,b) in denen a UND b endzustand sind. Selbes gilt für den Startzustand

Nun müssen die Kanten hinzugefügt werden:
Zwischen 2 Zuständen (ai,b),(aj,b) wird eine Kante aus A hinzugefügt wenn A die Kante (ai,aj) enthält. Übergangszeichen ist dann das der Kante zugeordnete.
Das Selbe gilt für die Kanten aus B.

//edit (korrektur):
Der Automat muss zum Schluss noch angepasst werden. Wenn von einem Zustand (a1,b1) ein Zeichen für beide Automaten einen übergang erzeugt (also (a1,b1)->(a2,b1) und (a1,b1)->(a1,b2)) dann müssen diese Übergänge noch zusammengefasst werden auf (a1,b1)->(a2,b2))