Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

endliche Automaten
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> endliche Automaten
 
Autor Nachricht
Caidian
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2008
Beiträge: 7

BeitragVerfasst am: 08 Sep 2008 - 15:33:59    Titel: endliche Automaten

Ich habe zwei Fragen

1.) was schreibt man bei endlichen Automaten an die Kante zu den Fangzuständen (es gibt ein Zeichen (kombination) die für alle anderen Zeichen steht die, die Wörter repräsentiert, die beim Übergang des selben zustands in einen anderen nicht gebraucht wurden aber ich habe es leider vergessen und weder Skript noch google hilft mir weiter)?

2.) Es seien 2 Automaten zweier Sprachen gegeben und das Ziel sei einen Vereinigungsautomaten zu bilden.

Meine Theorie:

Beide Automaten parallel schalten:

A) bei NICHT-Deterministischen endlichen Automaten würde ich einen neuen Anfangszustand schaffen und jeweils mit einem Epsilon Übergang zu den Automaten eine Kante ziehen. Stimmt das?

B) Deterministischen endlichen Automaten: Wie ist es da?

Vielleicht könnt ihr mir weiterhelfen.
Danke schon im Vorraus!
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.07.2008
Beiträge: 3004
Wohnort: Gießen

BeitragVerfasst am: 08 Sep 2008 - 15:41:09    Titel:

zu

1.) das große sigma bezeichnet alle zeichen des alphabets und mengenoperationen auf sprachen sind anwendbar, vielleicht hilft das weiter

2.)

a) klingt nachvollziehbar

b) stichwort "zustandspaare" - du durchläufst beide dea parallel Wink
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 08 Sep 2008 - 15:55:28    Titel:

Kennst du den Produktautomat? Dieser erkennt den Schnitt zweier regulärer Sprachen. Man kann durch eine einfache Modifikation einen Vereinigungsautomaten daraus machen.

Gegeben zwei deterministische Automaten

A1 = (Q1, Sigma, d1, s1, F1)
A2 = (Q2, Sigma, d2, s2, F2)

Qi : Zustandsmenge
Sigma : Alphabet
di : Transitionsfunktion
si : Startzustand
Fi : Menge der Endzustände

Der Produktautomat ist so definiert:

A1xA2 = (Q1xQ2, Sigma, d, [s1, s2], F1xF2) mit

d([q1, q2], a) = [d1(q1, a), d2(q2, a)] wobei [q1, q2] ein Zustand aus Q1xQ2 ist.

Dieser Automat erkennt den Schnitt. Um nun die Vereinigung zu erhalten muss man lediglich die Endzustände ändern. Diese sind nicht F1xF2 sondern (F1xQ2) U (Q1xF2), sprich in einem Zustandspaar [q1, q2] müssen nicht beide Zustände akzeptierend sein sondern mindestens einer.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> endliche Automaten
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum