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

Question

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

[ РЕДАКТИРОВАТЬ: Чтобы уточнить , ОП хочет принять регулярное выражение в качестве ввода, и программносоздать машину Тьюринга для выполнения той же задачи.OP пытается выполнить задачу создания регулярного выражения TM из , а не с использованием регулярного выражения.]

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

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

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

Простой (то есть: "aaa", "bbb", "abcde"): это листовой класс, у которого нет подвыражений

ComplexWithoutOr(т.е.: "a (ab) *", "(a (ab) c (b) ) *"): этот класс содержит список регулярных выражений.

ComplexWithOr (то есть: "a (a | b) ", "(a ((ab) | c (b) ) "): этот класс содержитОперация Or, которая содержит список RegularExpression и представляет часть «a | b» первого примера и «(ab) | c (b) » второго.

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

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

Когда дело доходит доПоколение МТ, у меня разные уровни сложности:

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

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

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

"(ab) abac ": это выражение ComplexWithoutOr, которое содержит выражение ComplexWithOr" (ab)"(которое имеет простое выражение внутри" ab ") и простое выражение" abac "

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

Затем он генерирует MT3 для "abac".Выход МТ2 это вход МТ3.Вывод MT3 является результатом выполнения

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

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

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

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

Answer 1

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

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

Answer 2

Майкл Сипсер, в Введение в теорию вычислений , доказывает в главе 1, что регулярные выражения эквивалентны конечным автоматам по своей описательной способности. Частью доказательства является построение недетерминированного конечного автомата (NDFA), который распознает язык, описываемый конкретным регулярным выражением. Я не собираюсь копировать половину этой главы, что было бы довольно сложно из-за используемой системы обозначений, поэтому я предлагаю вам взять или купить книгу (или, возможно, поиск в Google, использующий эти термины, покажет подобное доказательство) и использовать это доказательство как основа для вашего алгоритма.

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

Answer 3

в иерархии chomsky регулярное выражение - Level3, тогда как TM - Level1.это означает, что TM может производить любое регулярное выражение, но не наоборот.