Привет, еще один читатель, я снова с новой главой в этой серии высокоуровневого введения в теорию вычислений, и если вы новичок в этой серии, я поставлю ссылку на первую часть, где мы немного говорили о алфавиты, языки и DFA в блоге гик-культуры прямо здесь.

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

— НФА

Чтобы свести к минимуму сложность многих переходов и многих состояний, мы считаем с угадывающей силой NFA, которая в основном создает несколько копий машины, чтобы угадать, в каком состоянии она должна быть, и если вся последовательность считана, а экземпляр машины в конечном состоянии автоматы распознают язык, и наоборот, если копия автомата не может продолжаться, она просто удаляется

И мы можем видеть по автоматам, что пример слева распознает двоичный язык, который содержит {0,1}, где последний символ последовательности равен 1, но мы также можем заметить, что есть два перехода, когда я читаю символ 1 в тот же момент NFA пытается угадать, является ли тот, который мы читаем, последним или находится в середине последовательности.

Если мы читаем последовательность 011, автоматы прочитают ноль и останутся в состоянии p, но когда мы прочитаем 1, NFA создаст еще одну копию машины (аналогично второму процессу в операционной системе) одну из копий останется в состоянии p, а другой перейдет в q, и после этого NFA прочитает последнюю 1, и экземпляр машины, которая была в p, будет удален, потому что я читаю символы в состоянии, которое есть никаких переходов и машина, которая была в состоянии p, создаст другую копию в состоянии q машина, которая читала последнюю в состоянии p, не будет иметь никаких символов для чтения и не будет принята машиной, но копия с q в активном состоянии больше не будет символов для чтения, и как только q станет конечным состоянием, будет принята последовательность 011.

И теперь, когда мы рассмотрим основной рабочий процесс NFA, если вы спрашиваете себя: «NFA лучше, чем DFA?». Ответ — нет, и DFA, и NFA математически эквивалентны, и обе машины могут распознавать обычные языки, главное отличие в том, что с NFA я не знаю точно, где находится машина, потому что я могу иметь много состояний во многих копиях машина, но я получаю возможность угадывать, используя NFA, не нужно указывать каждую транзакцию, и, в конце концов, если у вас есть язык и вам нужно доказать, что этот язык является обычным языком, вы можете создать NFA, DFA или регулярное выражение они все эквивалентны, и в случае успеха ваш язык, безусловно, является обычным языком

- Регулярные выражения

Вы, вероятно, слышали о регулярных выражениях раньше и, вероятно, также скопировали регулярное выражение из переполнения стека, и вы не были очень уверены, как оно работает, ну, теперь вы знаете, что регулярные выражения являются частью области теории вычислений, но в отличие от NFA и DFA регулярное выражение генерирует последовательность обычного языка вместо распознавания.
Свойства регулярных выражений:

— Union
Подобно оператору or, я могу генерировать последовательности, содержащие один или другой символ, например, в языке, где у меня есть символы [A, B]. Я могу представить это с помощью A U B (A или B).

— Конкатенация
Это похоже на клей между элементами, я могу генерировать последовательности, содержащие оба символа, как в языке, где у меня есть символы [A, B], я могу представить это с помощью A . Б (АБ).

— Звездный оператор
Его экспоненциальное повторение символа, случайным образом идущего от 0 до бесконечности, как в языке, где у меня есть символ [A]. Я могу представить это с помощью A* ({}, A, AA, AAA, A… н).

Давайте создадим последовательность в первом NFA для языка: "{0,1}, где последний символ последовательности равен 1". наше регулярное выражение будет 0*.1*.1

Приведенные выше регулярные выражения могут генерировать все возможные входные данные для описанного языка, и мне просто нужно было сгенерировать звездочку для символов 0 и 1, которые могут генерировать символы *n(звезда с целым числом n), а затем соедините символы 0* и 1* и, наконец, я просто добавил последний .1 в полезное выражение, например, если мое n равно нулю, моя последовательность будет пустой (без символов 0 и 1), и последовательность будет отклонена NFA, но если я добавлю последний 1 символ NFA перейдет непосредственно в конечное состояние и примет последовательность

Сегодняшняя статья немного короче предыдущей, но теперь, когда я рассмотрел NFA и регулярные выражения, я все еще продолжаю рекомендовать вам углубиться в теорию вычислений, это очень зрелая тема в компьютерных науках, а также очень увлекательная со многими приложениями в реальном мире. Мир.

Я также хочу поблагодарить всех вас за то, что вы прочитали мою последнюю статью, было здорово, что мы попали в URL-адреса разработчиков, и статью пригласили опубликовать в блоге гик-культуры. Так благодарен за всех вас, ребята.

Теперь, когда мы рассмотрели DFA, NFA и регулярные выражения в темах теории вычислений, нам еще многое предстоит изучить, например, грамматики свободного контекста, автомат выталкивания вниз, машины Тьюринга, грамматику и многое другое, так что следите за обновлениями. До встречи :)