Ein nicht deterministischer endlicher Automat ist eine endliche Zustandsmaschine, bei der ein Tupel auf mehrere Zustände abgebildet wird. Dh Wir ersetzen die übliche Übergangsfunktion eines DFA durch eine andere Funktion .$(state,symbol)$$\delta : Q \times \Sigma \to Q\ $$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$

Wenn Sie wissen, was eine NFA ist, können Sie den nächsten Abschnitt überspringen.

Formale Definition

Eine NFA wird von eindeutig beschrieben

• eine endliche Menge von Zuständen$Q$
• eine endliche Menge von Symbolen$\Sigma$
• die Übergangsfunktion$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$
• der Ausgangszustand$q_0 \in Q$
• eine Menge von Endzuständen$F \subseteq Q$

Die Maschine beginnt in und liest eine endliche Kette von Symbolen w ∈ & Sigma; * , für jedes Symbol wird es gleichzeitig die Übergangsfunktion Funktion mit einem aktuellen Zustand anzuwenden und jeden neuen Satz von Zuständen auf den Satz von aktuellen Zuständen hinzuzufügen.$q_0$$w \in \Sigma^*$

Herausforderung

Für diese Aufgabe werden wir ignorieren , um sie zu vereinfachen. Außerdem besteht das Alphabet immer aus den (Klein-) Buchstaben a bis z und die Menge der Zustände für eine nicht negative ganze Zahl N ist { 0 … N } . Der Ausgangszustand ist immer 0 .$F\ $$\texttt{a}\ $$\texttt{z}\ $$\{0 \dots N\}$$N$$0$

Mit einem gegebenen Wort und einer Beschreibung der NFA besteht Ihre Aufgabe darin, alle Endzustände zu bestimmen.$w \in \{\texttt{a}\dots\texttt{z}\}^*$

Beispiel

Betrachten Sie die Zeichenfolge und die folgende Beschreibung:$\texttt{abaab}$

state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]

Die Maschine startet in :$q_0 = 0$

1. lese ein : neue Staaten { 1 $\texttt{a}$$\{1\}$
2. lese a : neue Staaten { 1 , 2 $\texttt{b}$$\{1,2\}$
3. lese ein : new states { 0 $\texttt{a}$$\{0\}$
4. lese ein : neue Staaten { 1 $\texttt{a}$$\{1\}$
5. lese a : neue Staaten { 1 , 2 $\texttt{b}$$\{1,2\}$

Die Endzustände und damit die Ausgabe wären also .$\{1,2\}$

Hinweis: In Schritt (2) wird der Übergang von Zustand auf ∅ abgebildet, da die Beschreibung nur Übergänge zu nicht leeren Mengen enthält.$2$$\emptyset$

Regeln

Die Eingabe besteht aus einem String und einer Beschreibung der NFA (ohne -Übergänge):$\epsilon$

• Die Eingabezeichenfolge ist immer ein Element von $\{\texttt{a}\dots\texttt{z}\}^*$
• gültige Eingaben (nicht beschränkt auf):
  • Liste / Array von Tupeln / Listen
  • durch neue Zeile getrennte Eingabe
• Die Beschreibung des NFA enthält nur Übergänge mit nicht leeren Mengen als Ergebnis
  • Sie können Regeln mit den gleichen Zeichen abkürzen , wenn deren Ergebnis das gleiche ist (z. B. Regeln 0,'a',[1,2]und 0,'b',[1,2]könnte mit abgekürzt0,"ab",[1,2]
  • Sie können jede Regel separat nehmen (zB Regel 0,'a',[1,2]kann 0,'a',[1]und sein 0,'a',[2])
• Sie können auch Großbuchstaben wählen, wenn Sie möchten
• Sie können die Anzahl der Zustände als Eingabe verwenden
• Sie können davon ausgehen, dass die Eingaben in einer bestimmten Reihenfolge vorliegen (z. B. sortiert nach Bundesstaat oder Symbolen).

Die Ausgabe ist eine Liste / Menge / durch neue Zeilen getrennte Ausgabe usw. der Endzustände

• Ordnung spielt keine Rolle
• keine Duplikate (als Set)

Testfälle

Diese Beispiele werden in dem Format sein , description word -> stateswo Sie descriptioneine Liste von Tupeln (state,symbol,new-states):

[]  "x" -> []
[]  "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])]  "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])]  "abc" -> []
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])]  "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])]  "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])]  "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])]  "abb" -> [1,2]

Haskell , 66 Bytes

import Data.List
f d=foldl(\s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

Probieren Sie es online!

Brachylog , 42 Bytes

,0{hẸ&t|∋₁B∋IhJ&tJ&hhC∧I∋₁C∧It∋S&hb;B,S↰}ᵘ

Eingabe als [string, nfa] wobei nfa eine Liste von Zustandsübergängen ist [Anfangszustand, Buchstabe, neue Zustände als Liste]

Erläuterung

,0                                              # Append 0 to the input (initial state)
  {                                      }ᵘ     # Find all unique outputs
   h                                            # if first element (string)
    Ẹ                                           #   is empty
     &t                                         #   then: return last element (current state)
       |                                        #   else:
        ∋₁B                                     #       save the state transitions in "B"
           ∋I                                   #       take one of these transitions, save in "I"
             hJ                                 #       take the initial state requirement, store in "J"
               &tJ                              #       make sure "J" is actually the current state
                  &hhC                          #       Save first char of string in C
                      ∧I∋₁C                     #       make sure the char requirement for the state transition is the current char
                           ∧It∋S                #       Make "S" equal to one of the new states
                                &hb             #       Behead the string (remove first char)
                                   ;B,S         #       Add B (the state transitions) and S (the new state)
                                       ↰        #       recur this function

Probieren Sie es online!

Brachylog v2, 31 Bytes

{b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐtt}ᵘ

Probieren Sie es online!( oder mit einem komplexeren Beispiel )

Brachylog ist wirklich gut in dieser Art von Problemen und wirklich schlecht in Problemen, die zwei separate Eingänge und einen Ausgang erfordern. Fast das ganze Programm ist nur Sanitär.

Das Eingabeformat ist eine Liste mit zwei Elementen: Das erste ist die Liste der Statusübergänge ( [oldState, symbol, newState]) und das zweite ist die Liste der Symbole. Ursprünglich plante ich dieses Programm, um mit Zeichencodes für Symbole zu arbeiten (da Brachylogs Umgang mit Zeichenfolgen manchmal etwas seltsam sein kann), aber es stellt sich heraus, dass Zeichen auch funktionieren (obwohl Sie die Eingabezeichenfolge als Liste von Zeichen schreiben müssen, nicht als ein Faden). Wenn ein Zustand-Symbol-Paar in mehrere verschiedene Zustände übergehen kann, schreiben Sie mehrere Übergänge, um damit umzugehen.

Erläuterung

{b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐtt}ᵘ
{                            }ᵘ   Find all distinct outputs that can result from:
 b                                  taking the input minus its first element,
  ,Ȯ                                appending a singleton list (i.e. an element)
    ,Ȯ                              then appending that same element again
      \                             and transposing;
       c                            then concatenating the resulting lists,
        ↔,0↔                        prepending a 0,
            ġ₃                      grouping into blocks of 3 elements
              k                       (and discarding the last, incomplete, block),
               H&                   storing that while we
                 h                  take the first input element,
                  g  z              pair a copy of it with each element of
                   ;H                 the stored value,
                      {  }ᵐ         assert that for each resulting element
                       ∋ᵈ             its first element contains the second,
                        ᵈ ᵐ           returning the list of second elements,
                            t       then taking the last element of
                           t          the last element.

Es ist wahrscheinlich einfacher, dies zu verfolgen, indem Sie sich ansehen, was einige Teilversionen des Programms hervorbringen würden. Verwenden Sie jedes Mal die folgenden Eingaben:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

wir können die Ausgaben einiger Präfixe dieses Programms beobachten:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃k
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

Für das erste Beispiel ist hier Lzunächst ein unbekanntes Element, aber wenn wir es über transponieren\ , erkennt Brachylog, dass die einzige Möglichkeit eine Liste mit der gleichen Länge wie die Eingabe ist. Das letzte Beispiel ist hier nicht deterministisch; Wir modellieren den Nichtdeterminismus in der NFA mithilfe des Nichtdeterminismus in Brachylog.

Mögliche Verbesserungen

Ein Teil der Syntax hier, wie ↔,0↔und vor allem das Durcheinander H&hg;Hz{…ᵈ}ᵐ, ist ziemlich klobig. Es würde mich nicht überraschen, wenn es einen genaueren Weg gäbe, dies auszudrücken.

{∋ᵈ}ᵐist an sich eine ziemlich verdächtige Struktur - man würde erwarten, dass man nur schreiben kann ∋ᵈᵐ- aber sie wird aus irgendeinem Grund nicht analysiert.

Python 3, 103 80 Bytes

danke an @BWO

w=lambda n,f,a={0}:w(n,f[1:],{y for(x,c,y)in n if c==f[0]and{x}&a})if''<f else a

TIO

Vorheriges "elegantes" Listenverständnis (103 Bytes):

def w(a,b):
    q=[0]
    for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
    return q

JavaScript (ES6), 99 Byte

Übernimmt die Eingabe als (nfa)(string). Gibt ein Set zurück.

a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,[])):new Set(s)

Probieren Sie es online!

R , 81 Bytes

function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

Probieren Sie es online!

Einfache Antwort mit Reduce. Nimmt Regeln als drei Vektoren von state, symbol, new-statesaufgerufen a,b,e.

Regeln sind getrennt (zB Regel 0,'a',[1,2]ist 0,'a',1und 0,'a',2).

Kokosnuss , 64 Bytes

d->reduce$((s,c)->{r for(*y,r)in d for S in s if[S,c]==y},?,{0})

Probieren Sie es online!

Sauber , 68 Bytes

Diese, die auf der Haskell-Lösung von ovs basiert, ist etwas kürzer als mein ursprünglicher Ansatz.

Enthält jetzt ein Testgeschirr

import StdEnv
?d=foldl(\s c=removeDup[r\\(y,r)<-d,g<-s|(g,c)==y])[0]

Probieren Sie es online!

Kohle , 44 Bytes

⊞υ⁰Ｆη«≔υζ≔⟦⟧υＦζＦθ¿∧⁼§λ⁰κ⁼§λ¹ιＦ§λ²¿¬№υμ⊞υμ»Ｉυ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

⊞υ⁰

Drücken Sie 0auf die vordefinierte leere Liste, um den Anfangszustand auf zu setzen$\{0\}$.

Ｆη«

Schleife über den Eingang.

≔υζ

Kopieren Sie den Zustand.

≔⟦⟧υ

Setzen Sie den Zustand zurück.

Ｆζ

Schleife über die Kopie des Staates.

Ｆθ

Schleife über die NFA-Einträge.

¿∧⁼§λ⁰κ⁼§λ¹ι

Wenn der Eintrag übereinstimmt, dann ...

Ｆ§λ²

... Schleife über die neuen Staaten ...

¿¬№υμ

.... wenn sie noch nicht in der Liste sind ...

⊞υμ»

... füge sie der Liste hinzu.

Ｉυ

Konvertieren Sie die Liste der Status in eine Zeichenfolge für die implizite Ausgabe in separaten Zeilen.

Perl 6 , 61 54 Bytes

->\n,\s{set +s&&reduce {n.grep(*[^2]⊆@_)[*;2]},0,|s}

Probieren Sie es online!

Nimmt eine Liste von Statusübergängen und eine Eingabezeichenfolge als Liste von Zeichen.

Japt , 31 Bytes

W=[W]c;Ê?ßUÅVVf!øW føUg)mÌc):Wâ

Versuch es!

2 Bytes gespart, wobei Japts Fähigkeit, aus einigen Eingaben implizit eine Funktion zu bilden, besser genutzt wurde

Erläuterung:

W=[W]c;                            Initialize the state set to [0] on the first run
       Ê?                   :Wâ    If the input is empty return the unique states; else...
             Vf!øW                 Get the transitions valid for one of the current states
                   føUg)           Of those, get the ones valid for the current character
                        mÌc)       Merge the states of the remaining transitions
         ßUÅV                      Repeat with the remaining characters as input

Der neue Code "Zustände initialisieren" könnte etwas detaillierter sein. Japt initialisiert Wauf 0 , wenn es weniger als 3 - Eingänge sind, so auf dem ersten Durchlauf [W]ist [0], und c„abflacht“ ein Array. [0]ist schon so flach wie es nur geht, also wird es nicht verändert. Bei nachfolgenden Läufen What beispielsweise ein anderer Wert [1,2]. In diesem Fall [W]wird [[1,2]]ein Einzelelement-Array, bei dem dieses Element ein Array ist. Dieses Mal cpackt es aus und geht zurück zu [1,2]. So ist es im ersten Lauf W=[0]und in den nachfolgenden Läufen W=W.