Un automate fini non déterministe est une machine à états finis dans laquelle un tuple est mappé à plusieurs états. C'est à dire. nous remplaçons la fonction de transition δ : Q × Σ → Q habituelle d'un DFA par une autre fonction Δ : Q × Σ → P ( Q ) .$(state,symbol)$$\delta : Q \times \Sigma \to Q\ $$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$

Si vous savez ce qu'est un NFA, vous pouvez ignorer la section suivante.

Définition formelle

Un NFA est uniquement décrit par

• Un ensemble fini d'états$Q$
• un ensemble fini de symboles$\Sigma$
• la fonction de transition$\Delta : Q \times \Sigma \to \mathcal{P}(Q)$
• l'état initial$q_0 \in Q$
• un ensemble d'états finaux$F \subseteq Q$

La machine démarre en et lit une chaîne finie de symboles w ∈ Σ ∗ , pour chaque symbole, elle appliquera simultanément la fonction de fonction de transition avec un état actuel et ajoutera chaque nouvel ensemble d'états à l'ensemble d'états actuels.$q_0$$w \in \Sigma^*$

Défi

Pour ce défi , nous ignorerons de la simplifier, en outre l'alphabet sera toujours les lettres (minuscules) a à z et l'ensemble des états sera { 0 ... N } pour un entier non négatif N . L'état initial sera toujours 0 .$F\ $$\texttt{a}\ $$\texttt{z}\ $$\{0 \dots N\}$$N$$0$

Étant donné un mot et une description du NFA, votre tâche consiste à déterminer tous les états finaux.$w \in \{\texttt{a}\dots\texttt{z}\}^*$

Exemple

Considérez la chaîne et la description suivante:$\texttt{abaab}$

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

La machine démarre en :$q_0 = 0$

1. lire un : nouveaux états { 1 $\texttt{a}$$\{1\}$
2. lire a : nouveaux états { 1 , 2 $\texttt{b}$$\{1,2\}$
3. lire un : nouveaux états { 0 $\texttt{a}$$\{0\}$
4. lire un : nouveaux états { 1 $\texttt{a}$$\{1\}$
5. lire a : nouveaux états { 1 , 2 $\texttt{b}$$\{1,2\}$

Ainsi, les états finaux et donc la sortie seraient .$\{1,2\}$

Remarque: à l' étape (2), la transition de l'état correspond à ∅ car la description inclut uniquement les transitions vers des ensembles non vides.$2$$\emptyset$

Règles

L'entrée consistera en une chaîne et une sorte de description du NFA (sans transitions ):$\epsilon$

• la chaîne d'entrée sera toujours un élément de $\{\texttt{a}\dots\texttt{z}\}^*$
• entrées valides (non limitées à):
  • liste / tableau de tuples / listes
  • entrée séparée par nouvelle ligne
• la description de la NFA ne contiendra que des transitions avec des ensembles non vides
  • vous pouvez abréger des règles avec les mêmes caractères si leur résultat est le même (par exemple des règles 0,'a',[1,2]et 0,'b',[1,2]pourrait être abrégé avec0,"ab",[1,2]
  • vous pouvez séparer chaque règle (par exemple, la règle 0,'a',[1,2]peut être 0,'a',[1]et 0,'a',[2])
• vous pouvez choisir des majuscules si vous le souhaitez
• vous pouvez prendre le nombre d'états en entrée
• vous pouvez supposer une sorte de classement des entrées (par exemple, triées par état ou symboles)

La sortie sera une sortie séparée par liste / ensemble / nouvelle ligne, etc. des états finaux

• l'ordre n'a pas d'importance
• pas de doublons (car c'est un ensemble)

Cas de test

Ces exemples seront au format description word -> statesoù se descriptiontrouve une liste de tuples (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 octets

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

Essayez-le en ligne!

Brachylog , 42 octets

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

entrée comme [chaîne, nfa] où nfa est une liste de transitions d'état [état initial, lettre, nouveaux états comme liste]

Explication

,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

Essayez-le en ligne!

Brachylog v2, 31 octets

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

Essayez-le en ligne! ( ou avec un exemple plus complexe )

Brachylog est vraiment bon dans ce genre de problème, et vraiment mauvais dans les problèmes qui nécessitent deux entrées séparées et une sortie. Presque tout ce programme n'est que de la plomberie.

Le format d'entrée est une liste contenant deux éléments: le premier est la liste des transitions d'états ([oldState, symbol, newState] ), et le second est la liste des symboles. J'ai initialement prévu que ce programme fonctionne avec des codes de caractères pour les symboles (car la gestion des chaînes de Brachylog peut être un peu bizarre parfois), mais il s'avère que les caractères fonctionnent aussi (bien que vous deviez écrire la chaîne d'entrée sous forme de liste de caractères, pas comme un string). Si une paire état-symbole peut passer à plusieurs états différents, vous écrivez plusieurs transitions pour y faire face.

Explication

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

Il est probablement plus facile de suivre cela en regardant ce que certaines versions partielles du programme produiraient. En utilisant à chaque fois l'entrée suivante:

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

nous pouvons observer les sorties de certains préfixes de ce programme:

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

Pour le premier exemple ici, Lest initialement un élément inconnu, mais lorsque nous le transposons via \, Brachylog se rend compte que la seule possibilité est une liste avec la même longueur que l'entrée. Le dernier exemple ici n'est pas déterministe; nous modélisons le non-déterminisme dans le NFA en utilisant le non-déterminisme dans Brachylog lui-même.

Améliorations possibles

Une partie de la syntaxe ici, comme ↔,0↔et surtout le désordre avec H&hg;Hz{…ᵈ}ᵐ, est assez maladroite. Cela ne me surprendrait pas s'il y avait une façon plus tordue de formuler cela.

{∋ᵈ}ᵐest en soi une structure assez suspecte - vous vous attendez à pouvoir simplement écrire ∋ᵈᵐ- mais elle n'analyse pas pour une raison quelconque.

Python 3, 103 80 octets

merci à @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

Compréhension de liste "élégante" précédente (103 octets):

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 octets

Prend l'entrée comme (nfa)(string) . Renvoie un ensemble.

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)

Essayez-le en ligne!

R , 81 octets

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

Essayez-le en ligne!

Réponse simple en utilisant Reduce. Prend les règles comme trois vecteurs d' state, symbol, new-statesappelsa,b,e .

Les règles sont distinctes (par exemple, la règle 0,'a',[1,2]est 0,'a',1et 0,'a',2).

Noix de coco , 64 octets

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

Essayez-le en ligne!

Nettoyer , 68 octets

Celui-ci basé sur la solution Haskell d'Ovs est un peu plus court que mon approche initiale.

comprend maintenant un harnais de test

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

Essayez-le en ligne!

Fusain , 44 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

⊞υ⁰

Appuyez 0sur la liste vide prédéfinie pour définir l'état initial sur$\{0\}$.

Ｆη«

Boucle sur l'entrée.

≔υζ

Copiez l'état.

≔⟦⟧υ

Réinitialisez l'état.

Ｆζ

Faites une boucle sur la copie de l'état.

Ｆθ

Faites une boucle sur les entrées NFA.

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

Si l'entrée correspond, alors ...

Ｆ§λ²

... boucle sur les nouveaux états ...

¿¬№υμ

.... s'ils ne sont pas déjà dans la liste ...

⊞υμ»

... ajoutez-les à la liste.

Ｉυ

Convertissez la liste des états en chaîne pour une sortie implicite sur des lignes distinctes.

Perl 6 , 61 54 octets

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

Essayez-le en ligne!

Prend une liste de transitions d'état et une chaîne d'entrée comme liste de caractères.

Japt , 31 octets

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

Essayez!

Enregistrement de 2 octets avec une meilleure utilisation de la capacité de Japt à former implicitement une fonction à partir de certaines entrées

Explication:

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

Le nouveau code "initialiser les états" pourrait utiliser un peu plus de détails. Japt initialise Wà 0 s'il y a moins de 3 entrées, donc sur la première course [W]est [0], et c« aplatit » un tableau. [0]est déjà aussi plat que possible, il n'est donc pas modifié. Par exemple, lors des exécutions suivantes W, sa valeur est différente [1,2]. Dans ce cas, [W]devient [[1,2]]un tableau à un élément où cet élément est un tableau. Cette fois, cela cdéballe et revient [1,2]. Ainsi, lors de la première exécution, c'est W=[0]et lors des exécutions suivantes, c'est W=W.