[Perl] Машина Тьюринга

Gudleifr> Ни у кого не завалялась реализация на Perl Машины Тьюринга (или другого достаточно сложного конечного автомата)?

Это как? МТ и конечный автомат — это две очень разные вещи. Вот регулярные выражения и конечные автоматы — одно и то же по мощности выражения.

<удалено по просьбе администрации>

Gudleifr> Меня не интересует вычислительная мощность. Меня интересует красивая запись состояний и переходов между ними. Плюс, возможность вынесения "за скобки" общей части. Моей Perl-изобретательности хватило только на следующее (там варьируются только ф-ии фывода - массив p - чтение и разбор происходят одинаково):

Реализация МТ и конечного автомата — две очень разные вещи. Просто это надо понимать. Если тебе нужен автомат, то могу рассказать, как сделано у нас. На С++, но идея от этого не меняется. Если ты хочешь именно МТ (а там и лента, и состояния, и алфавит, и действия совершенно другие)


Gudleifr> Другие варианты, например с представлением состояний в виде ф-ий выглядели еще страшнее. Но, думаю, бывалый Perl-овец напишет гораздо красивее.

База — символ алфавита и указатель на ф-цию, которая должна быть вызвана, а так же указатель на состояние, на которое надо перейти. Само состояние имеет символ состояний и список баз. Это принимаемые символы. При попадании в определённое состояние ожидается входной символ. После этого происходит поиск по списку. Найдено — значит перешли в новое состояние, не найдено — автомат переходит в запрещённое состояние и полностью останавливается. Выделение общих частей происходит простым способом. Кодируется автомат первого уровня, а, когда общая часть отработана, то в ф-ции, которая отрабатывается при переходе, вызывается автомат второго уровня. При некоторой сноровке, автомамт легко программируется так, что его начальное и конечное состояние (и запрещённое) становятся текущими для "интерпретатора автоматов", а автомат, вызвавший подавтомат просто сидит на стеке и ждёт завершения подавтомата. Если применять объекты, то ещё проще, т.к. подавтомат всегда объект со своей программой и памятью, поэтому на остальную часть свои проблемы не проецирует. Программка автомата, как правило ручное заполнение массива объектов.

Mishka> Реализация МТ и конечного автомата — две очень разные вещи. Просто это надо понимать...
Спасибо, но понимать не надо. Надо написать 10 красивых строк на Perl.

Gudleifr> Спасибо, но понимать не надо. Надо написать 10 красивых строк на Perl.
Для реализации МТ — мне не надо.

<удалено по просьбе администрации>

<удалено по просьбе администрации>

<удалено по просьбе администрации>