Автоматы - Построить NFA, используя копии DFA - формальное определение NFA
Я пытаюсь научиться решать следующее упражнение. Я не понимаю, как начать, это ошеломляет. Я понимаю DFA, NFA и как конвертировать DFA в NFA. Я также понимаю формальные обозначения.
Это не домашнее задание, оно просто для учебы. У меня есть решение, но я не могу понять из этого также..
Если бы кто-то смог выполнить упражнение ELI5, которое было бы удивительным, примеры таких упражнений (с надлежащими объяснениями) тоже были бы хорошими, я еще не нашел подобное упражнение в Интернете.
Дано:
Алфавит Σ
Символ c ∈ Σ
Обычный язык L над Σ
Язык Lc = {uv | ucv ∈ L}
Пусть D = (Q, Σ,, q0, F) - DFA с ℒ(D)=L.
Покажите, как построить NFA N, используя копии D, такие что ℒ(N)=Lc. Укажите формальное определение N.
1 ответ
Я не собираюсь подробно описывать формальное определение. В основном вы можете использовать две копии DFA. В первом, который вы запускаете, он не имеет конечных состояний. Для каждого перехода из состояния p в состояние q, которое читается как c, вы добавляете переход, не считывающий ничего, что идет от p в первой копии до q во второй копии. Таким образом, вы пропустите ровно один пункт c. Как только вы попадаете во вторую копию, вы знаете, что AC был пропущен, и вы можете принять, если оставшиеся входные данные приводят к состоянию принятия.