Uma máquina de estados finitos não determinística é uma máquina de estado finito, onde um tuplo é mapeado para vários estados. Ou seja. substituímos a função de transição usual δ : Q × Σ → Q de um DFA por outra função Δ : Q × Σ → P ( Q ) .$(state,symbol)$$\delta : Q \times \Sigma \to Q\ $$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$

Se você sabe o que é um NFA, pode pular a próxima seção.

Definição formal

Um NFA é descrito exclusivamente por

• um conjunto finito de estados$Q$
• um conjunto finito de símbolos$\Sigma$
• a função de transição$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$
• o estado inicial$q_0 \in Q$
• um conjunto de estados finais$F \subseteq Q$

A máquina inicia em e lê uma sequência finita de símbolos w ∈ Σ ∗ , para cada símbolo aplicará simultaneamente a função de função de transição com um estado atual e adicionará cada novo conjunto de estados ao conjunto de estados atuais.$q_0$$w \in \Sigma^*$

Desafio

Para esse desafio, ignoraremos para simplificá-lo. Além disso, o alfabeto sempre será as letras (minúsculas) de a a z e o conjunto de estados será { 0 … $F\ $$\texttt{a}\ $$\texttt{z}\ $ para alguns não negativo inteiro N . O estado inicial será sempre 0 .$\{0 \dots N\}$$N$$0$

Dada a palavra e uma descrição do NFA, sua tarefa é determinar todos os estados finais.$w \in \{\texttt{a}\dots\texttt{z}\}^*$

Exemplo

Considere a cadeia e a seguinte descrição:$\texttt{abaab}$

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

A máquina iniciará em :$q_0 = 0$

1. leia um : new states { 1 $\texttt{a}$$\{1\}$
2. leia a : novos estados { 1 , 2 $\texttt{b}$$\{1,2\}$
3. leia um : new states { 0 $\texttt{a}$$\{0\}$
4. leia um : new states { 1 $\texttt{a}$$\{1\}$
5. leia a : novos estados { 1 , 2 $\texttt{b}$$\{1,2\}$

Portanto, os estados finais e, portanto, a saída seriam .$\{1,2\}$

Nota: Na etapa (2), a transição do estado mapeada para ∅, pois a descrição inclui apenas transições para conjuntos não vazios.$2$$\emptyset$

Regras

A entrada consistirá em uma string e algum tipo de descrição do NFA (sem transições ):$\epsilon$

• a string de entrada sempre será elemento de $\{\texttt{a}\dots\texttt{z}\}^*$
• entradas válidas (não limitadas a):
  • lista / matriz de tuplas / listas
  • entrada separada por nova linha
• a descrição do NFA conterá apenas transições com conjuntos não vazios como resultado
  • você pode abreviar regras com os mesmos caracteres se o resultado for o mesmo (por exemplo, regras 0,'a',[1,2]e 0,'b',[1,2]pode ser abreviado com0,"ab",[1,2]
  • você pode separar cada regra (por exemplo, regra 0,'a',[1,2]pode ser 0,'a',[1]e 0,'a',[2])
• você pode escolher letras maiúsculas, se quiser
• você pode pegar o número de estados como entrada
• você pode assumir algum tipo de ordenação das entradas (por exemplo, ordenada por estado ou símbolos)

A saída será uma saída separada da lista / conjunto / nova linha etc. dos estados finais

• ordem não importa
• sem duplicatas (como um conjunto)

Casos de teste

Estes exemplos estarão no formato em description word -> statesque descriptionhá uma lista de tuplas (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]

Experimente online!

Braquilog , 42 bytes

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

input as [string, nfa] onde nfa é uma lista de transições de estado [estado inicial, letra, novos estados como lista]

Explicação

,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

Experimente online!

Brachylog v2, 31 bytes

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

Experimente online! ( ou com um exemplo mais complexo )

O Brachylog é realmente bom nesse tipo de problema e muito ruim em problemas que exigem duas entradas e uma saída separadas. Quase todo esse programa é apenas encanamento.

O formato de entrada é uma lista que contém dois elementos: o primeiro é a lista de transições de estado ([oldState, symbol, newState] ) e o segundo é a lista de símbolos. Inicialmente, planejei esse programa para trabalhar com códigos de caracteres para símbolos (porque o tratamento de strings de Brachylog às vezes pode ser um pouco estranho), mas acontece que os caracteres também funcionam (embora você precise escrever a string de entrada como uma lista de caracteres, não como uma linha). Se um par de estado-símbolo pode fazer a transição para vários estados diferentes, você escreve várias transições para lidar com isso.

Explicação

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

Provavelmente é mais fácil seguir isso, observando o que algumas versões parciais do programa produziriam. Utilizando a seguinte entrada de cada vez:

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

podemos observar as saídas de alguns prefixos deste programa:

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

Para o primeiro exemplo aqui, Lé inicialmente um elemento desconhecido, mas quando o \transpomos, Brachylog percebe que a única possibilidade é uma lista com o mesmo comprimento da entrada. O último exemplo aqui é não determinístico; estamos modelando o não-determinismo na NFA usando o não-determinismo no próprio Brachylog.

Possíveis melhorias

Algumas das sintaxes aqui, como ↔,0↔e principalmente a bagunça H&hg;Hz{…ᵈ}ᵐ, são bastante desajeitadas. Não me surpreenderia se houvesse uma maneira mais tensa de lidar com isso.

{∋ᵈ}ᵐé uma estrutura bastante suspeita - você esperaria poder escrever ∋ᵈᵐ- mas não analisa por algum motivo.

Python 3, 103 80 bytes

graças a @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

Compreensão de lista "elegante" anterior (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 bytes

Toma entrada como (nfa)(string). Retorna um conjunto.

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)

Experimente online!

R , 81 bytes

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

Experimente online!

Resposta direta usando Reduce. Toma regras como três vetores de state, symbol, new-stateschamado a,b,e.

As regras são separadas (por exemplo, regra 0,'a',[1,2]é 0,'a',1e 0,'a',2).

Coco , 64 bytes

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

Experimente online!

Limpo , 68 bytes

Este baseado na solução Haskell da ovs é um pouco menor do que minha abordagem inicial.

agora inclui um equipamento de teste

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

Experimente online!

Carvão , 44 bytes

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

Experimente online! Link é a versão detalhada do código. Explicação:

⊞υ⁰

Pressione 0para a lista vazia predefinida para definir o estado inicial como$\{0\}$.

Ｆη«

Loop sobre a entrada.

≔υζ

Copie o estado.

≔⟦⟧υ

Redefina o estado.

Ｆζ

Faça um loop sobre a cópia do estado.

Ｆθ

Faça um loop sobre as entradas da NFA.

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

Se a entrada corresponder, então ...

Ｆ§λ²

... percorrer os novos estados ...

¿¬№υμ

.... se eles ainda não estão na lista ...

⊞υμ»

... adicione-os à lista.

Ｉυ

Transmitir a lista de estados para cadeia de caracteres para saída implícita em linhas separadas.

Perl 6 , 61 54 bytes

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

Experimente online!

Leva uma lista de transições de estado e uma sequência de entrada como lista de caracteres.

Japonês , 31 bytes

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

Tente!

Economizou 2 bytes com melhor uso da capacidade do Japt de formar implicitamente uma função a partir de algumas entradas

Explicação:

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

O novo código "initialize states" pode usar um pouco mais de detalhes. Japt inicializa Wa 0 se houver menos do que 3 entradas, de modo que na primeira execução [W]é [0], e c"achata" uma matriz. [0]já é o mais plano possível, portanto não é alterado. Nas execuções subsequentes, Wtem um valor diferente, por exemplo [1,2]. Nesse caso , [W]torna-se [[1,2]]uma matriz de elemento único em que esse elemento é uma matriz. Desta vez, cdesembrulha isso e volta a [1,2]. Assim, na primeira execução é W=[0]e nas execuções subsequentes é W=W.