Есть ли какие-нибудь не конечные автоматы?

В теории автоматов мы все читаем автоматы как конечные автоматы с самого начала. Я хочу знать, почему автоматы конечны? Чтобы было понятно, что в автомате конечного - алфавит, язык, строки, созданные с помощью регулярных выражений, или что? И есть ли (в теории) какие-нибудь не конечные автоматы?

Все модели автоматов, с которыми вы обычно сталкиваетесь, представлены конечным образом; в противном случае их было бы неисчислимо много, что означает, что они не охвачены моделями, полными по Тьюрингу. Или, в CS-думаю, они были бы бесполезны ».

«Конечные автоматы» называются конечными, потому что они имеют только конечный набор конфигураций (кроме входной строки). Например, у автоматов Pushdown есть стек, который может иметь произвольный контент - существует бесконечно много возможных конфигураций.

Примечание: конфигурации КПК по-прежнему представлены конечным образом! Фактически, любая вычислительная модель, которая попадает в вычислимость по Тьюрингу, должна иметь конечно представимые конфигурации, иначе ТМ не смогут их смоделировать.

1. Я сознательно игнорирую гиперкомпьютеры здесь для цели этого вопроса.

Полное название «конечное состояние автомат». Важнейшей частью является то, что состояние автомата может быть полностью охарактеризовано элементом некоторого конечного набора дискретных состояний. Это означает, что если (релевантное) состояние автомата включает в себя вещественную переменную, существует бесконечное число потенциальных состояний (за исключением конечности представлений с плавающей запятой), и автомат не является конечным.

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

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

Короче говоря, бесконечные автоматы теоретически хорошо определены, а иногда даже встречаются.

В конечном автомате есть немало конечности: количество состояний, размер основного алфавита и длины строк, принимаемых машиной.

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

На самом деле, в теории автоматов (которая во многом отходит от происхождения Клини, Рабина и Скотта) существует множество видов автоматов, которые не являются конечными. Это возникает по нескольким причинам.

Пуштаун , например, автоматы, которые имеют бесконечный набор конфигураций (они имеют конечное число состояний, но реальность такова, что их следует рассматривать как «бесконечные автоматы»).

В том же духе есть и другие примеры бесконечных автоматов, для которых пространство состояний бесконечно, но с большой структурой. Например, мы рассматриваем класс автоматов, которые имеют в качестве пространства состояний векторное пространство (конечной размерности) и как функции перехода линейные отображения (плюс некоторые начальные и конечные вещи). Они известны как взвешенные автоматы над базовым полем (по Шютценбергеру в 61). Они могут быть сведены к минимуму и проверены на равенство. Другие примеры включают в себя регистровые автоматы (эти автоматы имеют конечный набор регистров и работают над бесконечным алфавитом: они могут сравнивать буквы с регистрами и хранить буквы в регистрах) и более современную форму именных автоматов.(которые имеют такую ​​же выразительность, но имеют лучшие основы и свойства). Пустота таких автоматов разрешима.

$A^*$$a$$u$$ua$и состояние принимает, если оно принадлежит L). Существует также конечный объект (который имеет в качестве языков состояний!). Существование этих двух объектов является одним из способов объяснить на высоком уровне, почему детерминированные автоматы могут быть минимизированы и тесно связаны с конгруэнцией Майхилла-Нерода.

В заключение, существуют бесконечные автоматы, но модели, которые впервые изучаются в лекции, всегда являются конечными.

Я думаю, что вопрос состоит в том, чтобы сделать вывод, что автоматов с бесконечным состоянием не существует, их просто не стоит поднимать.

В теории автоматов существует иерархия полномочий различных виртуальных моделей. У того, который я выучил, было 4 (что я помню, это было какое-то время), у того, что я нашел в Википедии, есть 5. Самый слабый в обоих автоматах конечного состояния, и самый сильный - машины Тьюринга. Существует некоторая концепция уровня, более мощного, чем машины Тьюринга, который условно называют гиперкомпьютером. Многие различные описания виртуальных машин попадают в один из этих уровней. Машины Тьюринга особенно известны многочисленными моделями, имеющими одинаковый уровень вычислительной мощности.

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

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

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

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