Регулярное выражение равной длины для разворота языка

Question

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

Исходная задача определена в формальных терминах здесь:

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

У меня нет проблем с доказательством того, что регулярные языки закрываются при развороте, но ограничение длины делает его намного сложнее. Пожалуйста, помогите мне, если вы можете, спасибо!

Answer 1

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

Пример: ab(c|d*e) ->(ed*|c)ba

Answer 2

Мы должны сделать индукцию по структуре регулярных выражений. Схема состоит в следующем: детали необходимо заполнить:

для терминала w, w^R = w и, следовательно, очевидно, w | = | w^R |.

для регулярного выражения (w_1 | w_2), с | w_1^R | = | w_1 | и | w_2^R | = | w_2 |, имеем (w_1 | w_2)^R = (w_1^R | w_2^R) и, следовательно, | (w_1 | w_2) | = | (w_1 | w_2)^R |

для регулярного выражения w * с | w | = | w^R |, то w *^R = w^R *, и, следовательно, | w * | = | w *^R |

для регулярного выражения w_1w_2 с | w_1 | = | w_1^R | и | w_2 | = | w_2^R |, имеем (w_1w_2)^R = w_2^Rw_1^R, и, следовательно, | w_1w_2 | = | w_1 | + | w_2 | = | w_1^R | + | w_2^R | = | w_2^Rw_1^R |

Здесь необходимо доказать, что L (w * R) = L (w^R *) и L^R (w_1w_2) = L (w_2^Rw_1^R).