NFA для алфавитов в матричной форме

Question

Я хочу помочь с моим заданием. Я могу понять, что это не то место, где вы найдете кого-то, кто сделает вашу домашнюю работу, поэтому я также попробовал другие сайты, такие как CHEGG Study, с той же информацией об учетной записи (сообщая вам, что это не приходит в голову, я не пытаюсь), но все же никто не может чтобы помочь мне пройти через это. Поэтому я подумал, что, попробовав другие варианты, я тоже должен обратиться за помощью. Опять же, я могу понять, что это не место, где вы выполняете свое задание, но, тем не менее, это место, где я могу найти помощь, которая поможет мне понять концепции. Пожалуйста, постарайтесь изо всех сил упростить вещи, так как я очень слаб в этом вопросе, и у меня не так много времени осталось, осталось пару часов. Я потратил время на изучение чегга. Я загружаю картинку

Answer 1

Часть 2: переименуйте четыре вектора a, b, c и d. Правила для допустимых шаблонов следующие:

1. a должно сопровождаться либо a, либо c;
2. b должно сопровождаться либо a, либо c;
3. * За 1033 * должно следовать либо b, либо d;
4. d должно сопровождаться либо b, либо d;
5. строка не может начинаться с 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, q C и qD (и, необязательно, q0) принимают, и QX нет. qX - это мертвое состояние, которое посещается, когда DFA знает достаточно о входных данных, чтобы отклонить его.

Часть 3: переименуйте векторы, как в части 2. Правила для допустимых шаблонов следующие:

1. все строки состоят из целого числа блоков;
2. допустимые фрагменты: aaa, aba, a cc, ad c, baa, bbb, b cc, bdd, ca c, cb c, cca, cda, da c, 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 терпит крах; это можно сделать в эквивалентном DFA, заполнив отсутствующие переходы и переведя их go в новое мертвое состояние (как qX в последнем примере).