非确定性有限自动机 (NFA) 校正

Question

我正在尝试解决有关 NFA 的问题。指令如下：字母{a, b, c}。 • L1 是最后一个字符与倒数第五个字符相同的所有字符串。例如，应该接受字符串 aaacbacbca，因为倒数第五个字符和最后一个字符都是 a。应该拒绝字符串 ccaab，因为倒数第五个字符是 c 而最后一个字符是 b。这是我想出的，但我真的是这个话题的初学者，我不确定是否正确：

Answer 1

您目前的自动机只接受以 acbca 结尾的字符串。以下是解决问题的步骤：

更改您拥有的自动机，使其接受所有具有最后一个和倒数五个符号的字符串 a
对符号 b、c
组合 3 个自动机

Answer 2

你几乎是对的，但是你画的自动机只接受以acbca结尾的字符串。这个会接受你想要的字符串

a,b,c     a      a,b,c   a,b,c   a,b,c    a     a,b,c
,--->[q0]--->[q1]--->[q2]--->[q3]--->[q4]--->{q5}----+>[q16]-----.
|    /|   b      a,b,c   a,b,c   a,b,c    b     a,b,c|   ^ a,b,c |
`---´ +----->[q6]--->[q7]--->[q8]--->[q9]--->{q10}---+   `-------´
      |   c      a,b,c   a,b,c   a,b,c    c     a,b,c|
      `----->[q11]-->[q12]-->[q13]-->[q14]-->{q15}---´

像 {q5} 这样的状态是接受状态，而像 [q0] 这样的状态不接受。 q16 的含义是确保两个相等字母相距 4 个字符但不以该字符结尾的字符串下沉到不接受状态。对于状态 [q4] 中的字母 b,c、状态 [q9] 中的字母 a,c 以及状态 [q14] 中的字母 a,b 可能也是如此，但是为了绘图清晰，我省略了它们。

非确定性有限自动机 (NFA) 校正

Nondeterministic finite automata (NFA) correction

regex

string

algorithm

logic

nfa