#automata #finite-automata
#автоматы #конечные автоматы
Вопрос:
Во время изучения лекции по классу автоматов у меня есть действительно основной вопрос в nfa.
Q0-a> Q1-лямбда>Q2
Если график выглядит так (я пока не могу публиковать изображения, К вашему сведению Q0-a> Q1 означает, что есть ребро (q0, q1) с меткой a) Могу ли я сказать, что дельта (q0, a) = q2? Я думаю, что мой вопрос немного глуп, но я хочу знать ответ!
Ответ №1:
Да, если график выглядит как
(q0) --a--> (q1) --e--> (q2)
Тогда справедливо сказать, что
delta(q0, a) = (q1)
Теперь это не означает, что (q1) это единственное состояние, из которого можно получить, (q0) используя одно a . Вместо этого, что обычно делается, определяется другая функция delta* , возможно, из пар наборов состояний и символов в другие наборы состояний, так что
delta*({(q0)}, a) = {(q1), (q2)}
Если вы хотите быть уверены, укажите домен и кодомен delta , чтобы устранить любую путаницу.
Комментарии:
1. Прежде всего, спасибо за ваш любезный ответ. Но на самом деле я запутался в обозначениях. Во-первых, можно ли использовать в nfa такие обозначения, как deleta*({qi}, w)= {qk, qj}? Потому что я вижу это обозначение только в dfa в моем учебнике. Во-вторых, очевидно, что я могу использовать delta * (q0, a) = q2, но могу ли я использовать delta (q0, a) = q1? Насколько мне известно, просто дельта без обозначения * не может использоваться в этом случае, но я не уверен.. спасибо agian за вашу доброту! Хорошего дня!!
2. Ой, опечатка в 7-й строке. дельта (q0,a)= q2
3. @Sung-WooHwang Отказ от ответственности — люди создают математику, и многие вещи являются простыми соглашениями. Существует несколько эквивалентных и правильных способов определения NFA; некоторые могут использовать delta: Q x S -> Q, некоторые могут напрямую использовать delta *: 2 ^ Q x S -> 2 ^ Q, некоторые могут даже использовать Q x S -> 2 ^ Q, если они включают лямбда-замыкание в правой части. Действительно, для NFA функция должна быть похожа на delta: Q x S -> 2 ^ Q, поскольку несколько переходов могут оставить одно и то же состояние для одного и того же символа. Даже тогда можно сказать, что delta(q0, a) = {(q1)} и различать delta *(q0, a) = {(q1),(q2)}.
4. Большое спасибо!! 😄😄