Gegeben sei der deterministische endliche Automat

´A = ({a, b}, {z_0, z_1, z_2, z_3, z_4, z_5}, z_0, {z_0, z_2}, delta)´

mit der folgenden Überführungsfunktion ´delta´:

´delta´ ´z_0´ ´z_1´ ´z_2´ ´z_3´ ´z_4´ ´z_5´
´a´ ´z_1´ ´z_4´ ´z_1´ ´z_0´ ´z_4´ ´z_2´
´b´ ´z_3´ ´z_2´ ´z_5´ ´z_4´ ´z_4´ ´z_4´

Konstruiere den zu ´A´ äquivalenten minimalen deterministischen endlichen Automaten.

Approach

Man betrachtet alle Paare von Zuständen (wobei man statt ´z_i´ nur ´i´ schreibt)

´{: ("(0,0)", "(0,1)", "(0,2)", "(0,3)", "(0,4)", "(0,5)"), ("(1,0)", "(1,1)", "(1,2)", "(1,3)", "(1,4)", "(1,5)"), ("(2,0)", "(2,1)", "(2,2)", "(2,3)", "(2,4)", "(2,5)"), ("(3,0)", "(3,1)", "(3,2)", "(3,3)", "(3,4)", "(3,5)"), ("(4,0)", "(4,1)", "(4,2)", "(4,3)", "(4,4)", "(4,5)"), ("(5,0)", "(5,1)", "(5,2)", "(5,3)", "(5,4)", "(5,5)") :}´

und streicht zuerst die Paare, bei denen genau eine Komponente in ´F´ liegt, und erhält

´{: ("(0,0)", , "(0,2)", , , ), (, "(1,1)", , "(1,3)", "(1,4)", "(1,5)"), ("(2,0)", , "(2,2)", , , ), (, "(3,1)", , "(3,3)", "(3,4)", "(3,5)"), (, "(4,1)", , "(4,3)", "(4,4)", "(4,5)"), (, "(5,1)", , "(5,3)", "(5,4)", "(5,5)") :}´

Wir streichen nun die Paare ´(i, j)´, bei denen von den Paaren ´(delta(i, a), delta(j, a))´ und ´delta(i, b)´, ´delta(j, b)´ mindestens eines schon gestrichen wurde. Dadurch entsteht (bei einem gestrichenen Paar, geben wir den Buchstaben ´x´ an, der zu einem gestrichenen Paar führt)

´{: ("(0,0)", , "(0,2)", , , ), (, "(1,1)", , "a", "b", "b"), ("(2,0)", , "(2,2)", , , ), (, "a", , "(3,3)", "a", "(3,5)"), (, "b", , "a", "(4,4)", "a"), (, "b", , "(5,3)", "a", "(5,5)") :}´

Man führt diesen Schritt erneut aus, findet dabei aber in diesem Fall kein zu streichendes Paar mehr. Aus der Tabelle kann man nun die Äquivalenzklassen lesen:

´K_0 = {z_0, z_2}´, ´K_1 = {z_1}´, ´K_3 = {z_3, z_5}´, ´K_4 = {z_4}´

ab, und erhalten den Automaten.


Solution

  • ´({a, b}, {K_0, K_1, K_3, K_4}, K_0, delta', {K_0})´

    mit

    ´delta´ ´K(0)´ ´K(1)´ ´K(3)´ ´K(4)´
    ´a´ ´K(1)´ ´K(4)´ ´K(0)´ ´K(4)´
    ´b´ ´K(3)´ ´K(0)´ ´K(4)´ ´K(4)´
  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Transform
  • Duration: 40min
  • Credits: 4
  • Difficulty: 0.7
  • Tags: hpi deterministic finite automaton
  • Note:
    HPI, 2014-07-03, Theoretische Informatik 2, Blatt 12, Aufgabe 1
  • Created By: adius
  • Created At:
    2014-07-23 14:37:13 UTC
  • Last Modified:
    2014-07-23 14:37:13 UTC