模拟NFA

Question

非确定性有限自动机是一个有限状态机，其中一个元组\( state，符号)\$映射到多个状态。即。我们用另一个函数\\ DFA：Q\倍数\Sigma \到\mathcal{P}(Q)\$替换了一个常用的\\Δ:Q\倍\Sigma \到Q\转换函数。

如果您知道NFA是什么，您可能想跳过下一节。

形式定义

NFA是由

• 一个有限的状态集
• 一组有限的符号
• \\Delta:Q\倍\Sigma \to \mathcal{P}(Q)\转换函数
• \$q_0 \in Q\$初始状态
• F \subseteq q\a组最后状态

机器以\$q_0\$启动并读取有限的符号字符串(w \in \Sigma^*)，对于每个符号，它将同时应用具有当前状态的转换函数，并将每个新的状态集添加到当前状态集中。

挑战

对于这个挑战，我们将忽略\\f\f \$F\ \$，而且字母表将始终是(小写)字母\\texttt{a}\texttt{z}\ \$，对于某些非负整数\$ N，状态集为\{0 \dots N}\$。初始状态总是\ \$0\$。

给定一个单词\\w \in {\texttt{a}\dots\texttt{z}}**$和NFA的描述，您的任务是确定所有的最终状态。

示例

考虑字符串\$\texttt{abaab}\$和以下描述：

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

机器将以\$q_0 =0\$启动：

1. 阅读\$\texttt{a}\$：新的状态\$$1}\$
2. 阅读\$\\texttt{b}\$：新状态\${1,2}\$
3. 阅读\$\texttt{a}\$：新状态\${0}\$
4. 阅读\$\texttt{a}\$：新的状态\$$1}\$
5. 阅读\$\\texttt{b}\$：新状态\${1,2}\$

因此，最后的状态，从而输出将是{1，2}\$。

注意：在步骤(2)中，状态\$2\$映射到\$\emptyset\$的转换只包括到非空集的转换。

规则

输入将包括一个字符串和NFA的某种描述(没有\$\epsilon\$-转换)：

• 输入字符串将始终是\${\texttt{a}\dots\texttt{z}^*\$的元素。
• 有效输入(不限于)：
  • 元组/列表数组
  • 新线分离输入

• NFA的描述将只包含以非空集作为结果的转换。
  • 如果结果相同，你可以用相同的字符缩写规则(例如。规则0,'a',[1,2]和0,'b',[1,2]可以用0,"ab",[1,2]缩写
  • 你可以把每条规则分开。规则0,'a',[1,2]可以是0,'a',[1]和0,'a',[2])

• 如果你愿意，你可以选择大写字母。
• 您可以将状态数作为输入。
• 你可以假设输入的某种顺序(例如。按状态或符号排列)

输出将是最后状态的列表/集/新行分隔输出等。

• 秩序不重要
• 没有重复(因为它是一组)

测试用例

这些示例将是格式description word -> states，其中description是元组(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]

Answer 1

哈斯克尔，66字节

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

在网上试试！

Answer 2

布氏对数，42字节

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

输入nfa是状态转换的列表。

解释

,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

在网上试试！

Answer 3

布氏对数 v2，31字节

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

在网上试试！ (或者用一个更复杂的例子)

Brachylog在这类问题上非常擅长，对于需要两个独立的输入和一个输出的问题也非常糟糕。几乎所有的程序都是水管。

输入格式是一个包含两个元素的列表:第一个是状态转换([oldState, symbol, newState])列表，第二个是符号列表。我最初计划这个程序使用符号的字符代码(因为Brachylog的字符串处理有时可能有点奇怪)，但结果是字符也能工作(尽管您必须将输入字符串写成字符列表，而不是字符串)。如果一个状态符号对可以转换到多个不同的状态，那么您可以编写多个转换来处理这个问题。

解释

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

通过查看程序的某些部分版本会产生什么结果，可能更容易遵循这一点。每次使用以下输入：

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

我们可以观察到这个程序的一些前缀的输出：

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

在这里的第一个例子中，L最初是一个未知的元素，但是当我们通过\转换它时，Brachylog意识到唯一的可能性是一个与输入长度相同的列表。这里的最后一个例子是非确定性的，我们在NFA中使用Brachylog本身的非确定性来建模非确定性。

可能的改进

这里的一些语法，比如↔,0↔，特别是与H&hg;Hz{…ᵈ}ᵐ的混乱，相当笨拙。如果有一种简洁的方式来表达这一点，我也不会感到惊讶。

{∋ᵈ}ᵐ本身是一种相当可疑的结构--您可能只希望能够编写∋ᵈᵐ --但由于某种原因，它不会解析。