Основные понятия теории
Теория автоматов – это раздел дискретной математики, изучающий математические модели автоматов и имеющий широкое применение в научных и прикладных исследованиях.
Такими автоматами могут быть как реальные устройства, так и абстрактные системы.
Теория автоматов позволяет доказывать разрешимость различных утверждений, записанных формальными средствами, с помощью математической логики и теории алгоритмов.
Теория формальных языков представляет собой формализацию лингвистики с использованием математических обозначений.
Формальный язык – это произвольное множество слов некоторого алфавита, которое позволяет создавать математическую модель реального языка.
Статья: Теория автоматов и формальных языков
Перечислим другие базовые понятия данной теории:
- Алфавит – это конечное непустое множество символов.
- Слово – это конечная последовательность символов из алфавита.
- Символ – это объект, имеющий собственное содержание и уникальную читаемую форму.
- Грамматика – это набор правил вывода, по которым одни слова можно преобразовывать в другие.
Автоматы, регулярные выражения и порождающие грамматики являются средствами конечного описания формального языка, позволяя применять эту теорию, так как на практике формальные языки чаще всего оказываются бесконечными.
Язык, определённый с помощью грамматики, удобен тем, что операции, производимые в ходе синтаксического анализа текста (т.е. анализ внутренней структуры текста на соответствие правилам естественного языка), можно сделать гораздо проще.
В настоящее время теория автоматов и формальных языков применяется в сфере искусственного интеллекта и, в частности, для создания чат-ботов.
Классификация грамматик
Известными способами создания грамматик формальных языков являются порождающие грамматики Хомского, а также окрестностные грамматики.
Окрестностные грамматики – это такой способ описания синтаксиса языка, когда каждому символу языка, находящемуся внутри цепочки, ставится в соответствие конечное число его окрестностей. Если каждый символ такой цепочки входит в неё вместе со всей заданной окрестностью, то она считается принадлежащей языку, созданному на основе окрестностной грамматики.
В зависимости от алгоритмического способа формирования языка принято выделять 3 вида грамматик:
- Распознающие грамматики. Представляют собой алгоритмы, которым в качестве входного параметра подаётся цепочка языка, а на выходе получается один из двух результатов: «yes» (если цепочка принадлежит языку) или «no» (если цепочка не принадлежит полностью языку).
- Порождающие грамматики. Такие алгоритмы используются в тех случаях, когда необходимо создавать цепочки языков по требованию. То есть они позволяют генерировать различные цепочки языков.
- Перечисляющие грамматики. Эти грамматики последовательно генерируют все цепочки языка. Если количество цепочек в языке бесконечно, то этот процесс перечисления всегда можно самостоятельно остановить в нужный момент времени, например, при получении требуемой цепочки.
При этом есть возможность преобразовывать виды грамматик от одной к другой. Например, для того чтобы преобразовать порождающую грамматику в перечисляющую, нужно создавать цепочки, упорядоченные по длине и порядку символов.
Однако, преобразовать перечисляющую грамматику к распознающей в общем случае нельзя, так как мощность распознающих грамматик меньше мощности порождающих и перечисляющих, и, как следствие, программа распознающей грамматики зациклится. Это надо учитывать, когда необходимо сравнивать порождающие грамматики Хомского и распознающие машины Тьюринга.
Тем не менее, можно использовать такой метод: после запуска алгоритма в ходе процесса перечисления цепочек ожидать цепочку, поданную на вход. Если она найдена, то заканчиваем процесс перечисления и делаем вывод, что она принадлежит этому языку.
Распознаватель автоматной грамматики
Распознавателем автоматной грамматики является конечный автомат.
Конечный автомат представляет собой частный вид машины Тьюринга, в которой на вход подаётся лента, с неё считываются символы, но при этом ничего не записывается.
На каждом шаге работы автомата считывается очередной символ, лента постепенно передвигается влево, и устройство управления осуществляет переход машины в новое состояние по определённым правилам перехода.
Автоматы-распознаватели отличаются от автоматов-преобразователей тем, что функции выходов и переходов не зависят от входных сигналов.
Конечные автоматы являются удобными инструментами для реализации логики искусственного интеллекта в различных играх. Они могут быть представлены в виде графа, что позволяет разработчику увидеть все возможные варианты.
Реализация конечного автомата с функциями-состояниями является достаточно простым и очень удачным методом реализации компьютерных игр.
Конечный автомат представим в виде графа, вершины которого являются состояниями, а рёбра – переходами между ними. Каждому ребру графа соответствует указатель, сообщающий, когда должен произойти очередной переход.
Выявляя состояния конечного автомата и переходы между ними, реализуем его.
Всякое состояние конечного автомата является функцией, которая вызывается при последующем обновлении кадра игры.
Для удобства можно использовать стек для управления состояниями игры. Так, в верхней части стека находится активное состояние, а переходы появляются при добавлении или удалении состояний из стека.
