矩阵形式字母表的 NFA

Question

我需要帮助完成我的作业。我能理解这不是一个你可以找人做作业的地方所以我也尝试了其他网站，比如 CHEGG study 使用相同的帐户信息（告诉你所以我没有想到它我没有尝试）但仍然没有人能够帮助我度过难关。所以我想在尝试其他选择之后我也应该在这里寻求帮助。同样，我可以理解这不是您完成作业的地方，但仍然是我可以找到帮助的地方，这将使我能够理解这些概念。请尽量简化事情，因为我在这门课上真的很弱，现在时间不多了，还有几个小时。我把时间浪费在了 chegg 研究上。我正在上传图片

Answer 1

第2部分：重命名四个向量a、b、c和d。有效模式规则如下：

a 后面必须跟 a 或 c；
b 后必须跟 a 或 c；
c 后必须跟 b 或 d;
d 后面必须跟 b 或 d；
字符串不能以 b 或 d 开头，因为它们在底部拉入 1

这表明以下 DFA：

 q  s  q'    q  s  q'    q  s q'     q  s q'     q  s q'     q  s q'
-- -- --    -- -- --    -- -- --    -- -- --    -- -- --    -- -- --
q0  a qA    qA  a qA    qB  a qA    qC  a qX    qD  a qX    qX  a qX
q0  b qX    qA  b qX    qB  b qX    qC  b qB    qD  b qB    qX  b qX
q0  c qC    qA  c qC    qB  c qC    qC  c qX    qD  c qX    qX  c qX
q0  d qX    qA  d qX    qB  d qX    qC  d qD    qD  d qD    qX  d qX

在此 DFA 中，所有状态 qA、qB、qC 和 qD（以及可选的 q0）都在接受，而 qX 不是。 qX 是死状态，一旦 DFA 足够了解输入以拒绝它，它就会被访问。

第 3 部分：按照第 2 部分重命名向量。有效模式的规则如下：

所有的字符串都是由整数个块组成的；
有效块是：aaa、aba、acc、adc、baa、bbb、bcc、bdd、cac、cbc、cca、cda、dac、dbd、dca、ddb。

这些的 NFA 如下所示：

 q  s  q'    q  s  q'    q  s  q'    q  s  q'    q  s  q'
-- -- --    -- -- --    -- -- --    -- -- --    -- -- --
q0  a qA    qA  a qAA   qB  a qBA   qC  a qCA   qD  a qDA
q0  b qB    qA  b qAB   qB  b qBB   qC  b qCB   qD  b qDB
q0  c qC    qA  c qAC   qB  c qBC   qC  c qCC   qD  c qDC
q0  d qD    qA  d qAD   qB  d qBD   qC  d qCD   qD  d qDD

  q  s  q'     q  s  q'     q  s q'      q  s q'
--- -- --    --- -- --    --- -- --    --- -- --
qAA  a q0    qBA  a q0    qCA  c q0    qDA  c q0
qAB  a q0    qBB  b q0    qCB  c q0    qDB  d q0
qAC  c q0    qBC  c q0    qCC  a q0    qDC  a q0
qAD  c q0    qBD  d q0    qCD  a q0    qDD  b q0

这里q0为接受状态（如果不接受空字符串，则新建状态q0'，只访问q0一次）。任何未描述的转换都表示 NFA 崩溃；这可以通过填充缺失的转换并让它们进入新的死状态（如上一个示例中的 qX）来制成等效的 DFA。

矩阵形式字母表的 NFA

NFA for Alphabets in Matrix Form

automata

nfa