Автоматы - Построить NFA, используя копии DFA - формальное определение NFA

Question

Я пытаюсь научиться решать следующее упражнение. Я не понимаю, как начать, это ошеломляет. Я понимаю DFA, NFA и как конвертировать DFA в NFA. Я также понимаю формальные обозначения.

Это не домашнее задание, оно просто для учебы. У меня есть решение, но я не могу понять из этого также..

Если бы кто-то смог выполнить упражнение ELI5, которое было бы удивительным, примеры таких упражнений (с надлежащими объяснениями) тоже были бы хорошими, я еще не нашел подобное упражнение в Интернете.

Дано:

• Алфавит Σ

• Символ c ∈ Σ

• Обычный язык L над Σ

Язык Lc = {uv | ucv ∈ L}

Пусть D = (Q, Σ,, q0, F) - DFA с ℒ(D)=L.

Покажите, как построить NFA N, используя копии D, такие что ℒ(N)=Lc. Укажите формальное определение N.

Answer 1

Я не собираюсь подробно описывать формальное определение. В основном вы можете использовать две копии DFA. В первом, который вы запускаете, он не имеет конечных состояний. Для каждого перехода из состояния p в состояние q, которое читается как c, вы добавляете переход, не считывающий ничего, что идет от p в первой копии до q во второй копии. Таким образом, вы пропустите ровно один пункт c. Как только вы попадаете во вторую копию, вы знаете, что AC был пропущен, и вы можете принять, если оставшиеся входные данные приводят к состоянию принятия.