Теория задач информатики

Я работаю над теорией задач информатики, но не могу заставить их работать:

а. Дайте NFA о распознавании языка (01 ∪ 001 ∪ 010)^*
б. Преобразуйте этот NFA в эквивалентный DFA. Укажите только ту часть DFA, которая достижима из начального состояния.

Я использую пакет automata.fa для кодирования автоматов и их тестирования. Вот примеры:

# example DFA syntax
example_dfa = DFA(
    states = {'q1', 'q2', 'q3', 'q4', 'q5'},
    input_symbols = {'0', '1'},
    transitions = {
        'q1': {'0': 'q1', '1': 'q2'},
        'q2': {'0': 'q1', '1': 'q3'},
        'q3': {'0': 'q2', '1': 'q4'},
        'q4': {'0': 'q3', '1': 'q5'},
        'q5': {'0': 'q4', '1': 'q5'}
    },
    initial_state='q3',
    final_states = {'q3'}
)

# example NFA syntax
example_nfa = NFA(
    states = {"q0", "q1", "q2"},
    input_symbols = {"0", "1"},
    transitions = {
        "q0": {"": {"q1", "q2"}},
        "q1": {"0": {"q1"}, "1": {"q2"}},
        "q2": {"0": {"q1"}, "1": {"q2"}},
    },
    initial_state = "q0",
    final_states = {"q1"},
)

# example regular expression syntax
example_regex = "(a*ba*(a|b)*)|()"

Для ответа на приведенный выше вопрос я попробовал использовать следующую диаграмму для NFA:

from automata.fa.nfa import NFA

prob_1_17a = NFA(
    states = {'q0', 'q1', 'q2', 'q3'},
    input_symbols = {'0', '1'},
    transitions = {
        'q0': {'0': {'q3'}, '1': {'q0'}},
        'q1': {'0': {'q1'}, '1': {'q0'}},
        'q2': {'0': {'q0'}, '1': {'q2'}},
        'q3': {'0': {'q1'}, '1': {'q2'}},
    },
    initial_state='q0',
    final_states = {'q0'}
)

но автогрейдер выдает следующий результат:

Полученные результаты:
Запускающая команда:
$ timeout 15 python3 unit_tests/unit_test_prob_1_17a.py
НЕОЖИДАННЫЙ РЕЗУЛЬТАТ НА ЭТИХ ВХОДНЫХ УСЛОВИЯХ:
['01', '00101', '01001', '01010', '010101', '00100101', '00101001', '00101010', '01000101', '01001001', ...]
Тест для: unit_test_prob_1_17a.py
Этот тест дал вам еще 0 баллов

Как разработать правильный NFA/DFA?

python computer-science dfa nfa

27.03.2024 02:11

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вашу попытку NFA можно визуализировать следующим образом:

Это неправильно. Например, он позволяет вводу начинаться с 1, что не допускается языком. Цикл в q₂ позволил бы входным данным иметь последовательные единицы, но это никогда не возможно. Цикл в q₁ позволит входным данным иметь любую последовательность нулей, но язык никогда не сможет принять строку, содержащую четыре или более последовательных нуля.

С другой стороны, ваша попытка не принимает действительный ввод «01», потому что после такого ввода состояние будет q₂, и это не является состоянием принятия в вашем NFA.

Как спроектировать НФА

Чтобы разработать NFA для языка (01 ∪ 001 ∪ 010)^*, мы могли бы сделать это шаг за шагом. Сначала создайте диаграмму для языка (01)^*:

q₀ — это состояние запуска и принятия, а q₄ — это приемник недопустимого ввода. Затем расширьте его до (01 ∪ 001)^*:

И затем доведите до (01 ∪ 001 ∪ 010)^*:

Как создать DFA из NFA

Чтобы спроектировать соответствующий DFA, определите состояние для каждого возможного набора состояний в NFA. Так, например, (𝑞₁,𝑞₂) — одно из таких состояний, а (𝑞₀,𝑞₁,𝑞₂) — другое. Таких состояний много, но реально достижимы лишь некоторые.

Используя конструкцию powerset, мы можем определить, какие входные префиксы приводят к каким состояниям в NFA, и мы можем назначить каждой уникальной комбинации состояний отдельное состояние DFA. Как только мы находим ту же комбинацию состояний NFA, с которой мы уже встречались, с другим префиксом, нам не нужно еще больше удлинять этот префикс, и поэтому мы получаем следующую таблицу возможностей:

префикс НФА заявляет состояние DFA ε 𝑞₀ 𝑞₀ 0 𝑞₁,𝑞₂ 𝑞₁₂ 00 𝑞₁ 𝑞₁ 000 𝑞₄ 𝑞₄ 001 𝑞₀ 𝑞₀ 01 𝑞₀,𝑞₃ 𝑞₀₃ 010 𝑞₀,𝑞₁,𝑞₂ 𝑞₀₁₂ 0100 𝑞₁,𝑞₂ 𝑞₁₂ 0101 𝑞₀,𝑞₃ 𝑞₀₃ 011 𝑞₄ 𝑞₄ 1 𝑞₄ 𝑞₄

Я выбрал имена для состояний DFA, которые отражают то, как они сопоставляются с набором состояний в NFA. Каждое состояние DFA, соответствующее комбинации состояний NFA, включающей 𝑞₀, является принятием.

Это приводит к следующему DFA:

Код Python

Вышеупомянутые NFA и DFA можно представить следующим образом:

nfa = NFA(
    states = {'q0', 'q1', 'q2', 'q3', 'q4'},
    input_symbols = {'0', '1'},
    transitions = {
        'q0': {'0': {'q1','q2'}, '1': {'q4'}},
        'q1': {'0': {'q4'},      '1': {'q0'}},
        'q2': {'0': {'q1'},      '1': {'q3'}},
        'q3': {'0': {'q0'},      '1': {'q4'}},
        'q4': {'0': {'q4'},      '1': {'q4'}} # Sink
    },
    initial_state='q0',
    final_states = {'q0'}
)

dfa = DFA(
    states = {'q0', 'q1', 'q12', 'q03', 'q012', 'q4'},
    input_symbols = {'0', '1'},
    transitions = {
        'q0'  : {'0': 'q12',  '1': 'q4' },
        'q12' : {'0': 'q1',   '1': 'q03'},
        'q1'  : {'0': 'q4',   '1': 'q0' },
        'q03' : {'0': 'q012', '1': 'q4' },
        'q012': {'0': 'q12',  '1': 'q03'},
        'q4':   {'0': 'q4',   '1': 'q4' } # Sink
    },
    initial_state='q0',
    final_states = {'q0', 'q03', 'q012'}
)

27.03.2024 15:12