Un autómata finito no determinista es una máquina de estados finitos donde una tupla se asigna a múltiples estados. Es decir. reemplazamos la función de transición habitual de un DFA con otra función .δ : Q × Σ → $(state,symbol)$$\delta : Q \times \Sigma \to Q\ $$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$

Si sabe qué es un NFA, puede saltear la siguiente sección.

Definicion formal

Un NFA se describe únicamente por

• $Q$ un conjunto finito de estados
• $\Sigma$ un conjunto finito de símbolos
• $\Delta : Q \times \Sigma \to \mathcal{P}(Q)$ la función de transición
• $q_0 \in Q$ el estado inicial
• $F \subseteq Q$ un conjunto de estados finales

La máquina comienza en y lee una cadena finita de símbolos , para cada símbolo aplicará simultáneamente la función de función de transición con un estado actual y agregará cada nuevo conjunto de estados al conjunto de estados actuales. w ∈ Σ $q_0$$w \in \Sigma^*$

Desafío

Para este desafío, ignoraremos para simplificarlo, además, el alfabeto siempre será las letras (minúsculas) to \ texttt {z} \ y el conjunto de estados será \ {0 \ puntos N \} para algunos no negativo número entero N . El estado inicial siempre será 0 .a z { 0 ... N } N $F\ $$\texttt{a}\ $$\texttt{z}\ $$\{0 \dots N\}$$N$$0$

Dada una palabra y una descripción de la NFA, su tarea es determinar todos los estados finales.$w \in \{\texttt{a}\dots\texttt{z}\}^*$

Ejemplo

Considere la cadena y la siguiente descripción:$\texttt{abaab}$

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

La máquina comenzará en :$q_0 = 0$

1. leer un : nuevos estados { 1 $\texttt{a}$$\{1\}$
2. lea a : nuevos estados$\texttt{b}$$\{1,2\}$
3. leer un : nuevos estados$\texttt{a}$$\{0\}$
4. leer un : nuevos estados$\texttt{a}$$\{1\}$
5. lea a : nuevos estados$\texttt{b}$$\{1,2\}$

Entonces, los estados finales y, por lo tanto, la salida serían .$\{1,2\}$

Nota: En el paso (2), la transición del estado asigna a ya que la descripción solo incluye transiciones a conjuntos no vacíos.$2$$\emptyset$

Reglas

La entrada consistirá en una cadena y algún tipo de descripción de la NFA (sin transiciones ):$\epsilon$

• la cadena de entrada siempre será elemento de $\{\texttt{a}\dots\texttt{z}\}^*$
• entradas válidas (no limitadas a):
  • lista / conjunto de tuplas / listas
  • entrada separada de nueva línea
• la descripción de la NFA solo contendrá transiciones con conjuntos no vacíos como resultado
  • puede abreviar reglas con los mismos caracteres si su resultado es el mismo (por ejemplo, reglas 0,'a',[1,2]y 0,'b',[1,2]podría abreviarse con0,"ab",[1,2]
  • puede tomar cada regla por separado (por ejemplo, la regla 0,'a',[1,2]puede ser 0,'a',[1]y 0,'a',[2])
• puedes elegir letras mayúsculas si quieres
• puede tomar el número de estados como entrada
• puede asumir algún tipo de orden de las entradas (por ejemplo, ordenado por estado o símbolos)

La salida será una salida separada por lista / conjunto / nueva línea, etc. de los estados finales

• el orden no importa
• sin duplicados (ya que es un conjunto)

Casos de prueba

Estos ejemplos estarán en el formato description word -> statesdonde descriptionhay una 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]

Pruébalo en línea!

Brachylog , 42 bytes

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

entrada como [cadena, nfa] donde nfa es una lista de transiciones de estado [estado inicial, letra, nuevos estados como lista]

Explicación

,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

Pruébalo en línea!

Brachylog v2, 31 bytes

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

Pruébalo en línea! ( o con un ejemplo más complejo )

Brachylog es realmente bueno en este tipo de problemas, y realmente malo en problemas que requieren dos entradas separadas y una salida. Casi todo este programa es solo fontanería.

El formato de entrada es una lista que contiene dos elementos: el primero es la lista de transiciones de estado ( [oldState, symbol, newState]) y el segundo es la lista de símbolos. Originalmente planeé este programa para trabajar con códigos de caracteres para símbolos (porque el manejo de cadenas de Brachylog puede ser un poco extraño a veces), pero resulta que los caracteres también funcionan (aunque debe escribir la cadena de entrada como una lista de caracteres, no como una cuerda). Si un par de estado-símbolo puede hacer la transición a varios estados diferentes, debe escribir varias transiciones para lidiar con eso.

Explicación

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

Probablemente sea más fácil seguir esto mirando lo que producirían algunas versiones parciales del programa. Usando la siguiente entrada cada vez:

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

Podemos observar los resultados de algunos prefijos de este 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 el primer ejemplo aquí, Linicialmente es un elemento desconocido, pero cuando lo transponemos vía \, Brachylog se da cuenta de que la única posibilidad es una lista con la misma longitud que la entrada. El último ejemplo aquí es no determinista; estamos modelando el no determinismo en la NFA usando el no determinismo en Brachylog.

Posibles mejoras.

Parte de la sintaxis aquí, como ↔,0↔y especialmente el desorden H&hg;Hz{…ᵈ}ᵐ, es bastante torpe. No me sorprendería si hubiera una forma más tersa de expresar esto.

{∋ᵈ}ᵐes, por derecho propio, una estructura bastante sospechosa (es de esperar que solo pueda escribir) ∋ᵈᵐ, pero no se analiza por alguna razón.

Python 3, 103 80 bytes

gracias 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

Anterior comprensión de la lista "elegante" (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). Devuelve un 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)

Pruébalo en línea!

R , 81 bytes

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

Pruébalo en línea!

Respuesta directa usando Reduce. Toma las reglas como tres vectores de state, symbol, new-statesllamadas a,b,e.

Las reglas son separadas (por ejemplo, la regla 0,'a',[1,2]es 0,'a',1y 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})

Pruébalo en línea!

Limpio , 68 bytes

Esta basada en la solución Haskell de ovs es un poco más corta que mi enfoque inicial.

ahora incluye un arnés de prueba

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

Pruébalo en línea!

Carbón , 44 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

⊞υ⁰

0$\{0\}$

Ｆη«

Pase sobre la entrada.

≔υζ

Copia el estado.

≔⟦⟧υ

Restablecer el estado.

Ｆζ

Pase sobre la copia del estado.

Ｆθ

Recorrer las entradas de NFA.

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

Si la entrada coincide, entonces ...

Ｆ§λ²

... recorrer los nuevos estados ...

¿¬№υμ

.... si aún no están en la lista ...

⊞υμ»

... agregarlos a la lista.

Ｉυ

Transmita la lista de estados a una cadena para la salida implícita en líneas separadas.

Perl 6 , 61 54 bytes

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

Pruébalo en línea!

Toma una lista de transiciones de estado y una cadena de entrada como lista de caracteres.

Japt , 31 bytes

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

¡Intentalo!

Se guardaron 2 bytes con un mejor uso de la capacidad de Japt para formar implícitamente una función a partir de algunas entradas

Explicación:

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

El nuevo código "inicializar estados" podría usar un poco más de detalle. Japt se inicializa Wa 0 si hay menos de 3 entradas, por lo que en la primera ejecución [W]es [0], y c"aplana" una matriz. [0]ya es tan plano como se pone, por lo que no se cambia. En ejecuciones posteriores Wtiene un valor diferente, por ejemplo [1,2]. En ese caso se [W]convierte en [[1,2]]una matriz de un solo elemento donde ese elemento es una matriz. Esta vez cdesenvuelve eso y vuelve a [1,2]. Por lo tanto, en la primera ejecución es W=[0]y en las ejecuciones posteriores es W=W.