Алгоритм генерации машины Тьюринга из регулярного выражения

Question

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

[EDIT: Чтобы уточнить, OP хочет принять регулярное выражение в качестве входного сигнала и программно сгенерировать машину Тьюринга для выполнения той же задачи. OP стремится выполнить задачу создания ТМ от регулярным выражением, а не с использованием регулярного выражения. ]

Сначала я объясню немного, что я сделал и то, что моя конкретная проблема:

Я моделировал регулярное выражение следующим образом:

RegularExpression (интерфейс): ниже классов реализует этот интерфейс

Simple (то есть: "ааа", "БББ", "ABCDE"): это класс лист не имеет каких-либо подвыражения

ComplexWithoutOr (то есть: "а (аб) *" , "(a (ab) c (b)) * "): этот класс содержит список RegularExpression.

ComplexWithOr (то есть: "а (а | б) ", "(а ((аb) | с (б) )"): этот класс содержит операцию, или, в котором содержится список RegularExpression (Ab) | c (b) "второго.

Переменная (то есть:" awcw ", где w E {a , b} *): это еще не реализовано, но идея состоит в том, чтобы моделировать его как лист-лист с некоторой другой логикой от Simple. Он представляет собой «w» часть примеров.

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

Когда дело доходит до поколения MT, у меня есть разные уровни сложности:

Простой: этот тип выражения уже работает. Создает новое состояние для каждой буквы и перемещается вправо. Если в каком-либо состоянии прочитанное письмо не является ожидаемым, оно запускает «схему отката», которая заканчивается головкой MT в исходном положении и останавливается в конечном состоянии.

ComplexWithoutOr: здесь возникает моя проблема. Здесь алгоритм генерирует MT для каждого подвыражения и объединяет их. Эта работа для некоторых простых случаев, но у меня проблемы с механизмом отката.

Вот пример, который не работает с моим алгоритмом:

«(аб) ДКС»: это выражение ComplexWithoutOr, который содержит выражение ComplexWithOr «(аб)» (то есть просто выражение внутри «ab») и простое выражение «abac»

Мой алгоритм генерирует сначала MT1 для «ab». Этот MT1 используется MT2 для «(ab) *», поэтому, если MT1 успешно, он снова возвращается в MT1, в противном случае откаты MT1 и MT2 заканчиваются вправо. Другими словами, MT2 не может потерпеть неудачу.

Затем он генерирует MT3 для «abac». Выход MT2 - это вход MT3.Выход MT3 является результатом выполнения

Теперь предположим, что эта строка ввода: «abac». Как видите, он совпадает с регулярным выражением. Поэтому давайте посмотрим, что произойдет, когда выполняется MT.

MT1 выполняется в первый раз «ab». MT1 терпит неудачу во второй раз «ac» и откатывает, ставя MT голову в 3-ей позицию «a». MT2 заканчивается справа, а вход отправляется в MT3. MT3 не работает, потому что «ac»! = «Abac». Таким образом, MT не распознает «abac».

Вы понимаете проблему? Вы знаете какое-либо решение для этого?

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

Answer 1

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

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

Answer 2

В иерархии хомского регулярное выражение - Уровень 3, тогда как ТМ - Уровень 1. это означает, что ТМ может создавать любое регулярное выражение, но не наоборот.

Answer 3

Michael Sipser, в Introduction to the Theory of Computation, доказывает в главе 1, что регулярные выражения эквивалентны конечным автоматам в их описательной мощности. Часть доказательства включает в себя построение недетерминированного конечного автомата (NDFA), который распознает язык, описываемый определенным регулярным выражением. Я не собираюсь копировать половину этой главы, что было бы довольно сложно из-за используемой нотации, поэтому я предлагаю вам взять или купить книгу (или, возможно, поиск Google с использованием этих условий станет аналогичным доказательством) и использовать это доказательство в качестве основы для вашего алгоритма.

Как машины Тьюринга могут моделировать NDFA, я предполагаю, что алгоритм для производства NDFA достаточно хорош.