Ist der Satz von Codes deterministischer Automaten mit endlichen Zuständen eine reguläre Sprache?

  • Sei $ \ Sigma $ ein gegebenes Alphabet. Gibt es eine Möglichkeit, deterministische Finite-State-Automaten (DFA) über $ \ Sigma $ als Zeichenfolgen von $ \ Sigma $ so zu codieren, dass die entsprechende Untermenge von $ \ Sigma ^ * $ eine reguläre Sprache ist?

    Zum Beispiel für Turingmaschinen ist der Satz von Codes von Turingmaschinen über ein festes Alphabet entscheidbar, und wir können von entscheidbaren Sets von Turingmaschinen (durch ihre Codes) sprechen.

    Natürlich können wir auch von regulären DFA-Mengen sprechen (durch ihre Codes). Ist die Menge aller DFAs in diesem Sinne regelmäßig?

    17 July 2012
    Kaveh
3 answers
  • Diese Antwort ist in gewisser Weise eine völlig betrügerische Herangehensweise, aber es ist tatsächlich möglich, alle DFAs als Zeichenfolgen zu codieren.

    Wir können einen DFA ausschreiben indem Sie seine Übergangstabelle ausschreiben. Wir können die Übergangstabelle mit nur 0s und 1s wie folgt ausschreiben: Schreiben Sie zuerst eine Anzahl von 1s aus, die der Anzahl der Zustände entspricht, und dann eine 0. Dann schreiben Sie eine Anzahl von 1s aus, die der Anzahl der Symbole in entspricht Alphabet, dann eine Null. Schreiben Sie dann jede Zeile der Übergangstabelle aus, indem Sie jeden Eintrag als Zahl von 1 ausschreiben, die angibt, in welchen Zustand übergegangen werden soll, und dann eine 1.

    Nun diese spezielle Kodierung eines DFA ist nicht regelmäßig. Was wir jedoch tun können, ist folgendes. Betrachten Sie die Menge aller solcher Kodierungen. Wir können sie dann in der Längen-Lex-Reihenfolge ordnen und dann die auf diese Weise hergestellten DFAs mit 0, 1, 2, 3, 4, ... usw. nummerieren, basierend auf ihrer Reihenfolge. In diesem Fall haben wir jetzt eine Schnittmenge zwischen $ \ mathbb {N} $ und der Menge aller DFAs. Von dort können wir dann die reguläre Sprache betrachten, die aus allen natürlichen Zahlen besteht, die binär geschrieben sind. Dieses Set ist definitiv regelmäßig; Hier ist ein regulärer Ausdruck dafür:

    0 | 1 (0 | 1) *

    Wir haben jetzt eine reguläre Sprache, die aus Kodierungen von DFAs besteht. Die Kodierung ist überhaupt nicht leicht zu bearbeiten - Sie müssten damit beginnen, alle Kodierungen von DFAs aufzulisten, bis Sie die gewünschte gefunden haben - aber mathematisch ist sie genau definiert.

    11 July 2012
    templatetypedef
  • DFAs können regelmäßig gespeichert werden:

    Wir nehmen an, dass $ \ # \ notin \ Sigma $ gilt und definieren

    $$ L = \ {\ # \ #e \ mide \ in \ {0,1 \} ^ * \} ^ * \ cdot \ {\ # s \ #b \ midb \ in \ {0 , 1 \} ^ *, s \ in \ Sigma \} ^ * \ quad, $$

    was eindeutig regulär ist. Dann für $ w \ in L $, so dass $ w = \ # \ # e_1 \ dots \ # \ # e_o \ # s_1 \ # b_1 \ # \ dots \ #s_n \ # b_n $ definiert wird

    $$ p_0 = 1, p_i = \ min \ {r_ {i-1}, n \} $$ wobei

    $$ r_i = \ min \ {j & gt; p_i \ mid \ existiert k, p_i \ leq k & lt; j: \ s_j = s_k \} $$

    ist der Index der ersten Symbolwiederholung nach $ p_i $. Sei $ \ {p_1, \ dots, p_k \} $ die auf diese Weise definierbare Menge. Jetzt erstellen wir ein DFA: Die Menge der Zustände lautet $ Q = \ {1, \ dots, m \} $, wobei $ m = \ max (\ {k \} \ cup \ {\ mathrm {bin} (b_i.) Ist ) \ mid 1 \ leq i \ leq n \}) $ und der Einfachheit halber wählen wir $ 1 $ als Startzustand. Die Menge der akzeptierenden Zustände lautet $ E = \ {\ mathrm {bin} (e_i) \ mid 1 \ leq i \ leq o \} $. Bei unserer Interpretation der Zeichenfolge $ w $ enthält jeder Teil $ \ # s_ {p_i} \ #, \ dots, \ # b_ {p_ {i + 1-1}} $ höchstens $ s \ in \ Sigma $ ein und für jeden solchen $ s $ eine binäre Zeichenfolge. Wir interpretieren diesen String als Ziel für unsere Übergangsfunktion $ \ delta: Q \ times \ Sigma \ bis Q $:

    $$ \ delta (i, s) = \ begin {cases} \ mathrm {bin} (b_j) & amp; \ besteht p_i, j: p_i \ leq j & lt; \ min \ {p_ {i + 1}, n \}, s_j = s \\ 1 & amp; \ text {else} \ end {cases} $$

    Nun ist $ (\ Sigma, Q, \ delta, 1, E) $ ein DFA. Andererseits ist es offensichtlich, dass jeder DFA auf diese Weise gespeichert werden kann (nachdem die Zustände umbenannt wurden).

    13 June 2013
    Ian Dickinson
  • Ich habe keine Ahnung, aber meine Intuition besagt, dass Sie das nicht könnten. Sie fragen im Grunde, ob Sie einen Regex-Matcher mit einem Push-Down-Automat implementieren können, und ich glaube nicht, dass Sie das können ... Der Regex-Ausdruck kann beliebig komplex sein. Es gibt also keine Möglichkeit, alle erforderlichen Zustände in den Zuständen des Pushdown-Automaten zu speichern. Daher müssen Sie den Pushdown zum Speichern des Zustands verwenden, in dem Sie sich befinden der Regex (und / oder das Wort) ... Und das Problem mit dem Push-Down ist, dass Sie nicht rückwärts fahren können, wenn Sie eine falsche Wendung im Regex nehmen (in einem normalen Automaten haben Sie einen Zustand.) Abdeckung für jeden falschen Zug möglich, da alle möglichen Kombinationen bekannt sind, wenn Sie die Anzahl der Zustände für den Automaten bestimmen, aber ich denke, dass dies im Push-Down-Verfahren erforderlich wäre, würde ein Backtracking erfordern, und ich glaube nicht, dass Sie dies implementieren können ) ...

    11 July 2012