[image]

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

Ни у кого не завалялась?
 
+
-
edit
 

Gudleifr

опытный

<удалено по просьбе администрации>
   38.038.0
Это сообщение редактировалось 23.01.2022 в 02:48
+
-
edit
 

Mishka

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

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

Gudleifr

опытный

<удалено по просьбе администрации>
   38.038.0
Это сообщение редактировалось 23.01.2022 в 02:46
+
-
edit
 

Mishka

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

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


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

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

Gudleifr

опытный

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

Mishka

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

Gudleifr

опытный

<удалено по просьбе администрации>
   41.041.0
Это сообщение редактировалось 23.01.2022 в 02:47
RU Gudleifr #06.01.2019 21:01  @Gudleifr#09.10.2015 09:59
+
-
edit
 

Gudleifr

опытный

<удалено по просьбе администрации>
   71.0.3578.9871.0.3578.98
Это сообщение редактировалось 23.01.2022 в 02:47
RU Gudleifr #03.01.2022 12:13  @Gudleifr#06.01.2019 21:01
+
-
edit
 

Gudleifr

опытный

<удалено по просьбе администрации>
   95.095.0
Это сообщение редактировалось 17.01.2022 в 23:20

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru