Niedeterministyczny skończony automat jest skończonej maszyny stanów, gdy krotka $(state,symbol)$ jest mapowany do wielu stanach. To znaczy. zastępujemy zwykłą funkcję przejścia DFA inną funkcją .$\delta : Q \times \Sigma \to Q\ $$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$

Jeśli wiesz, czym jest NFA, możesz pominąć następną sekcję.

Definicja formalna

NFA jest jednoznacznie opisany przez

• $Q$ skończony zbiór stanów
• $\Sigma$ skończony zestaw symboli
• $\Delta : Q \times \Sigma \to \mathcal{P}(Q)$ funkcja przejścia
• $q_0 \in Q$ stanie początkowym
• $F \subseteq Q$ zbiór stanów końcowych

Maszyna rozpoczyna od i czyta skończony ciąg symboli , dla każdego symbolu jednocześnie zastosuje funkcję przejścia z aktualnym stanem i doda każdy nowy zestaw stanów do zbioru stanów bieżących.$q_0$$w \in \Sigma^*$

Wyzwanie

Na to wyzwanie będziemy ignorować uproszczenie go, ponadto alfabet zawsze będzie (małymi literami) litery do Z oraz zbiór stanów będzie { 0 ... N } jakiegoś nieujemną liczbą całkowitą N . Stan początkowy zawsze będzie wynosił 0 .$F\ $$\texttt{a}\ $$\texttt{z}\ $$\{0 \dots N\}$$N$$0$

Biorąc pod uwagę słowo i opis NFA, Twoim zadaniem jest określenie wszystkich stanów końcowych.$w \in \{\texttt{a}\dots\texttt{z}\}^*$

Przykład

Rozważ ciąg i następujący opis:$\texttt{abaab}$

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

Maszyna uruchomi się w :$q_0 = 0$

1. przeczytaj : nowe stany { 1 $\texttt{a}$$\{1\}$
2. poczytać : nowe kraje { 1 , 2 $\texttt{b}$$\{1,2\}$
3. przeczytaj : nowe stany { 0 $\texttt{a}$$\{0\}$
4. przeczytaj : nowe stany { 1 $\texttt{a}$$\{1\}$
5. poczytać : nowe kraje { 1 , 2 $\texttt{b}$$\{1,2\}$

Zatem stany końcowe, a tym samym wynik wyniósłby .$\{1,2\}$

Uwaga: W kroku (2) przejście stanu odwzorowuje na ∅, ponieważ opis obejmuje tylko przejścia do niepustych zbiorów.$2$$\emptyset$

Zasady

Dane wejściowe będą składać się z łańcucha i pewnego rodzaju opisu NFA (bez -transitions):$\epsilon$

• ciąg wejściowy zawsze będzie elementem $\{\texttt{a}\dots\texttt{z}\}^*$
• prawidłowe dane wejściowe (nie ograniczone do):
  • lista / tablica krotek / list
  • wejście oddzielone nowym wierszem
• opis NFA będzie zawierał tylko przejścia z niepustymi zestawami
  • możesz skracać reguły tymi samymi znakami, jeśli ich wynik jest taki sam (np. reguły 0,'a',[1,2]i 0,'b',[1,2]można je skracać0,"ab",[1,2]
  • możesz wziąć każdą regułę osobno (np. reguła 0,'a',[1,2]może być 0,'a',[1]i 0,'a',[2])
• jeśli chcesz, możesz wybrać wielkie litery
• możesz przyjąć liczbę stanów jako dane wejściowe
• możesz założyć uporządkowanie wejść (np. uporządkowane według stanu lub symboli)

Dane wyjściowe będą oddzielonymi listami / zestawami / nowymi wierszami danymi wyjściowymi itd

• kolejność nie ma znaczenia
• bez duplikatów (ponieważ jest to zestaw)

Przypadki testowe

Te przykłady będą w formacie, w description word -> statesktórym descriptionznajduje się lista krotek (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 bajtów

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

Wypróbuj online!

Brachylog , 42 bajty

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

wprowadź jako [ciąg, nfa] gdzie nfa jest listą przejść między stanami [stan początkowy, litera, nowe stany jako lista]

Wyjaśnienie

,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

Wypróbuj online!

Brachylog v2, 31 bajtów

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

Wypróbuj online! ( lub z bardziej złożonym przykładem )

Brachylog jest naprawdę dobry w tego rodzaju problemach i bardzo źle w problemach, które wymagają dwóch osobnych danych wejściowych i wyjściowych. Prawie cały ten program to tylko hydraulika.

Format wejściowy to lista zawierająca dwa elementy: pierwszy to lista przejść między stanami ( [oldState, symbol, newState]), a drugi to lista symboli. Pierwotnie planowałem, aby ten program działał z kodami znaków dla symboli (ponieważ obsługa ciągów znaków Brachylog może być czasem trochę dziwna), ale okazuje się, że znaki też działają (chociaż musisz napisać ciąg wejściowy jako listę znaków, a nie jako ciąg). Jeśli para stan-symbol może przejść do wielu różnych stanów, piszesz wiele przejść, aby sobie z tym poradzić.

Wyjaśnienie

{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.

Prawdopodobnie łatwiej jest to sprawdzić, patrząc na niektóre częściowe wersje programu. Za pomocą następujących danych wejściowych za każdym razem:

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

możemy obserwować wyniki niektórych prefiksów tego programu:

[[[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]]

Pierwszy przykład tutaj Ljest początkowo nieznanym elementem, ale kiedy transponujemy go przez \, Brachylog zdaje sobie sprawę, że jedyną możliwością jest lista o tej samej długości co dane wejściowe. Ostatni przykład tutaj jest niedeterministyczny; modelujemy niedeterminizm w NFA za pomocą niedeterminizmu w samym Brachylogu.

Możliwe ulepszenia

Część składni tutaj, ↔,0↔a zwłaszcza bałagan z H&hg;Hz{…ᵈ}ᵐ, jest dość niezgrabna. Nie zdziwiłoby mnie to, gdyby istniał szybszy sposób na sformułowanie tego.

{∋ᵈ}ᵐsama w sobie jest dość podejrzaną strukturą - można by się było po prostu pisać ∋ᵈᵐ- ale z jakiegoś powodu nie analizuje.

Python 3, 103 80 bajtów

dzięki @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

Poprzednie „eleganckie” zestawienie listy (103 bajty):

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 bajtów

Pobiera dane wejściowe jako (nfa)(string). Zwraca zestaw.

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)

Wypróbuj online!

R , 81 bajtów

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

Wypróbuj online!

Prosta odpowiedź przy użyciu Reduce. Przyjmuje reguły jako trzy wektory state, symbol, new-statesnazywane a,b,e.

Reguły są osobne (np. Reguła 0,'a',[1,2]jest 0,'a',1i 0,'a',2).

Kokos , 64 bajty

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

Wypróbuj online!

Czysty , 68 bajtów

Ten oparty na rozwiązaniu ovas Haskell jest nieco krótszy niż moje początkowe podejście.

teraz zawiera uprząż testową

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

Wypróbuj online!

Węgiel drzewny , 44 bajty

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

⊞υ⁰

Naciśnij przycisk 0do wstępnie zdefiniowanej pustej listy, aby ustawić stan początkowy na$\{0\}$.

Ｆη«

Pętla nad wejściem.

≔υζ

Skopiuj stan.

≔⟦⟧υ

Zresetuj stan.

Ｆζ

Pętla nad kopią stanu.

Ｆθ

Pętla nad wpisami NFA.

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

Jeśli wpis pasuje, to ...

Ｆ§λ²

... zapętlać nowe stany ...

¿¬№υμ

.... jeśli nie ma ich na liście ...

⊞υμ»

... dodaj je do listy.

Ｉυ

Rzuć listę stanów na ciąg znaków, aby uzyskać niejawne dane wyjściowe w osobnych wierszach.

Perl 6 , 61 54 bajtów

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

Wypróbuj online!

Pobiera listę przejść stanu i ciąg wejściowy jako listę znaków.

Japt , 31 bajtów

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

Spróbuj!

Zaoszczędzono 2 bajty dzięki lepszemu wykorzystaniu zdolności Japt do niejawnego utworzenia funkcji z niektórych danych wejściowych

Wyjaśnienie:

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

Nowy kod „stanów inicjalizacji” może zawierać nieco więcej szczegółów. Japt inicjuje się Wna 0, jeśli jest mniej niż 3 wejścia, więc przy pierwszym uruchomieniu [W]jest [0]i c„spłaszcza” tablicę. [0]jest już tak płaski, jak się robi, więc się nie zmienia. Na przykład w kolejnych cyklach Wma inną wartość [1,2]. W takim przypadku [W]staje [[1,2]]się tablicą jednoelementową, której elementem jest tablica. Tym razem to crozpakowuje i wraca do [1,2]. Tak więc przy pierwszym uruchomieniu jest, W=[0]a przy kolejnych uruchomieniach jest W=W.