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

[Anonymous]

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

• Код: Выделить всё

  RegularExpression

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

• Код: Выделить всё

  Simple

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

• Код: Выделить всё

  ComplexWithoutOr

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

• Код: Выделить всё

  ComplexWithOr

  (пример: a(a|b)*, (a((ab)*|c(b)*)*): этот класс содержит операцию «ИЛИ» , который содержит список RegularExpression. Он представляет часть a|b первого примера и (ab)*|c(b)* второго.

• Код: Выделить всё

  Variable

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

Когда дело доходит до генерации машины Тьюринга (TM) , у меня разные уровни сложности:

Код: Выделить всё

Simple

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

Код: Выделить всё

ComplexWithoutOr

: вот и моя проблема. Алгоритм генерирует TM для каждого подвыражения и объединяет их. Это работает в некоторых простых случаях, но у меня проблемы с механизмом отката.
Описание проблемы
Вот пример ввода, для которого мой алгоритм дает сбой. :

Код: Выделить всё

(ab)*abac

: это выражение ComplexWithoutOr, которое содержит выражение ComplexWithOr (ab)* (внутри которого есть выражение Simple: ab) и Простое выражение abac
Мой алгоритм сначала генерирует TM1 для ab. Этот TM1 используется TM2 для (ab)*, поэтому в случае успеха TM1 он снова входит в TM 1, в противном случае TM1 выполняет откат и TM2 успешно завершает работу. Другими словами, TM2 не может дать сбой.
Затем он генерирует TM3 для abac. Выход TM2 является входом TM3. Выходные данные TM3 являются результатом выполнения.
Теперь предположим, что эта входная строка: abac. Как видите, оно соответствует регулярному выражению. Итак, давайте посмотрим, что происходит, когда TM выполняется.
TM1 выполняется успешно с первого раза: ab. TM1 терпит неудачу во второй раз для ac и выполняет откат, помещая головку TM в третьюrd позицию в a. TM2 завершается успешно, и ввод пересылается в TM3. TM3 не работает, поскольку ac не соответствует abac. Значит ТМ не распознает abac.
Это проблема. Как это решить?
Я использую Java для разработки, но язык не важен. Мой вопрос касается алгоритма.

Подробнее здесь: https://stackoverflow.com/questions/316 ... expression