Как показать, что «обратный» регулярный язык является регулярным

Я застрял в следующем вопросе:

«Регулярные языки - это как раз те, которые принимаются конечными автоматами. Учитывая этот факт, покажите, что если язык принят некоторым конечным автоматом, то также будет принят некоторым конечным; состоит из всех слов». из необратима «.L R L R$L$$L^{R}$$L^{R}$$L$

Таким образом, учитывая регулярный язык , мы знаем (по существу по определению), что он принят некоторыми конечными автоматами, поэтому существует конечный набор состояний с соответствующими переходами, которые переносят нас из исходного состояния в принимающее состояние тогда и только тогда, когда это строка в L . Мы можем даже настаивать на том, что есть только одно принимающее государство, чтобы упростить вещи. Чтобы принять обратный язык, все, что нам нужно сделать, это изменить направление переходов, изменить начальное состояние на состояние принятия и принять состояние на начальное состояние. Тогда у нас есть машина, которая «назад» по сравнению с оригиналом, и принимает язык L R .$L$$L$$L^{R}$

Вы должны показать , что всегда можно построить конечный автомат , который принимает строки в $L^R$ задан конечный автомат , который принимает строки в $L$ . Вот процедура, чтобы сделать это.

1. Переверните все ссылки в автомате
2. Добавить новое состояние (назовите его $q_s$ )
3. Нарисуйте ссылку, помеченную $\epsilon$ из состояния $q_s$ в каждое конечное состояние
4. Превратите все конечные состояния в нормальные состояния
5. Превратить начальное состояние в конечное состояние
6. Сделать $q_s$ начальным состоянием

Давайте формализуем все это; мы начнем с формулировки теоремы.

Теорема. Если $L$ является регулярным языком, то и $L^{R}$ .

Пусть $A = (Q_A, \Sigma_A, \delta_A, q_A, F_A)$ NFA и $L = L(A)$ . $\epsilon$ -NFA R определено ниже принимает язык L R .$A^{R}$$L^{R}$

1. $A^{R} = (Q_A \cup \{q_s\}, \Sigma_A, \delta_{A^R}, q_s, \{q_A\})$ и$q_s \notin Q_A$
2. $p \in \delta_A(q, a) \iff q \in \delta_{A^R}(p, a)$ , где$a \in \Sigma_A$ и$q, p \in Q_A$
3. $\epsilon-closure(q_s) = F_A$

Доказательство. Сначала докажем следующее утверждение: $\exists$ путь от $q$ до $p$ в $A$ помеченный буквой $w$ том и только в том случае, если $\exists$ путь от $p$ до $q$ в $A^R$ помеченный буквой $w^R$ (обратная $w$ ) для $q, p \in Q_A$ . Доказательством служит индукция по длине $w$ .

1. Базовый случай: $|w| = 1$
   Имеет место по определению $\delta_{A^R}$
2. Индукция: предположим, что утверждение верно для слов длины $\lt n$ и пусть $|w| = n$ и $w = xa$
   Пусть $p \in \delta_A^*(q, w) = \delta_A^*(q, xa)$
   Мы знаем, что $\delta_A^*(q, xa) = \cup_{p'}\delta_A(p', a)$ $\forall p' \in \delta_A^*(q, x)$
   $x$ и$a$ - слова, содержащие меньше$n$ символов. По предположению индукции,$p' \in \delta_{A^R}(p, a)$ и$q \in \delta_{A^R}^*(p', x^R)$ . Это означает, что$q \in \delta_{A^R}^*(p, ax^R) \iff p \in \delta_A^*(q, xa)$ .

Полагая $q = q_A$ и $p = s$ для некоторых $s \in F_A$ и заменяя $w^R$ для $ax^R$ гарантирует , что $q \in \delta_{A^R}^*(s, w^R)$ $\forall s \in F_A$ . Поскольку существует путь, помеченный $\epsilon$ из $q_s$ во все состояния в $F_A$ (3. в определении $A^R$) И путь от каждого состояния в $F_A$ в состоянии $q_A$ , меченного $w^R$ , то есть путь метил $\epsilon w^R = w^R$ от $q_s$ к $q_A$ . Это доказывает теорему.

Обратите внимание, что это доказывает, что $(L^R)^R = L$ также.

Пожалуйста, измените, если в моем доказательстве есть ошибки форматирования или недостатки ...

Для того, чтобы добавить к преобразованиям на основе автоматных , описанных выше, вы можете также доказать , что регулярные языки замкнуты при обращении, показывая , как преобразовать регулярное выражение для в регулярное выражение для L R . Для этого мы определим функцию R E V на регулярных выражениях , который принимает в качестве входных данных регулярного выражения R для некоторого языка L , а затем производит регулярное выражение R ' для языка L R . Это определяется индуктивно на структуре регулярных выражений:$L$$L^R$$REV$$R$$L$$R'$$L^R$

1. $REV(\epsilon) = \epsilon$
2. $REV(\emptyset) = \emptyset$
3. для любого a ∈ $REV(a) = a$$a \in \Sigma$
4. $REV(R_1 R_2) = REV(R_2) REV(R_1)$
5. $REV(R_1 | R_2) = REV(R_1) | REV(R_2)$
6. $REV(R*) = REV(R)*$
7. $REV((R)) = (REV(R))$

Вы можете формально доказать эту конструкцию правильно в качестве упражнения.

Надеюсь это поможет!

Используя регулярные выражения, докажите, что если регулярный язык, то \ emph {обращение} в L , L R = { w R : w ∈ L } , также регулярно. В частности, учитывая регулярное выражение , которое описывает L , показать по индукции , как превратить его в регулярное выражение , которое описывает L R . Ваше доказательство не должно прибегать к NFAs. $L$$L$$L^R=\{w^R: w\in L\}$$L$$L^R$

Мы будем предполагать , что задано регулярное выражение , которое описывает . Давайте сначала посмотрим на оператор конкатенации ( ∘ ), а затем мы можем перейти к более сложным операторам. Таким образом, наши случаи конкатенации имеют дело с длиной того, что конкатенируется. Итак, сначала мы разберем все конкатенации от a b до a ∘ b . При работе с ними разбейте компоненты как можно больше: ( a b ∪ a ) b → ( a b ∪ a ) ∘ $L$$\circ$$ab$$a\circ b$$(ab \cup a)b \rightarrow (ab \cup a) \circ b$, но вы, конечно, не можете нарушить ассоциативный порядок между различными представлениями.

Когда $\emptyset^R \rightarrow \emptyset$

Когда , у нас есть пустая строка, которая уже перевернута, поэтому механизм не меняется$s = \epsilon$

Когда это просто буква, как в s ∈ Σ , обращение это только эта буква, $s$$s \in \Sigma$$s$

Когда , у нас есть одна составляющая, поэтому мы просто обращаем эту составляющую в обратном направлении и, следовательно, σ $s = \sigma$$\sigma^R$

При , где к нечетно, мы имеем регулярное выражение , которое может быть записано в виде ( сг 0 ∘ сг 1 . . . Сг к - 1 ∘ сг к$s = (\sigma_0\sigma_1...\sigma_{k-1}\sigma_k)$$(\sigma_0\circ\sigma_1...\sigma_{k-1}\circ\sigma_k)$, Перестановка этих строк четной длины проста. Просто переключите индекс 0 с индексом k. Затем поменяйте индекс 1 с помощью индекса k-1. Продолжайте, пока каждый элемент не будет переключен один раз. Таким образом, последний элемент теперь является первым в регистре, а первый - последним. Второе - это второе, а второе - второе. Таким образом, у нас есть обратный регистр ex ex, который будет принимать обратную строку (первая буква является последней и т. Д.) И, конечно, мы обращаем каждую составляющую. Таким образом , мы получим $(\sigma_k^R\sigma_{k-1}^R...\sigma_{1}^R\sigma_0^R)$

При , где к четно, мы имеем регулярное выражение как правило , которое может быть записано в виде ( сг 0 ∘ сг 1 . . . σ к - 1 ∘ σ к$s = (\sigma_0\sigma_1...\sigma_{k/2}...\sigma_{k-1}\sigma_k)$$(\sigma_0\circ\sigma_1...\sigma_{k-1}\circ\sigma_k)$, Перестановка этих строк четной длины проста. Просто переключите индекс 0 с индексом k. Затем поменяйте индекс 1 с помощью индекса k-1. Продолжайте, пока каждый элемент не был переключен один раз, но элемент k / 2 (целое число, потому что k четное). Таким образом, последний элемент теперь является первым в регистре, а первый - последним. Второе - это второе, а второе - второе. Таким образом, у нас есть обратный регистр ex ex, который будет принимать обратную строку (первая буква является последней и т. Д.) И эта средняя буква. И, конечно, мы меняем каждую составляющую. Таким образом , мы получим $(\sigma_k^R\sigma_{k-1}^R...\sigma_{k/2}^R...\sigma_{1}^R\sigma_0^R)$

$\cup$$s_1, s_2$$s_1 \cup s_2$$s_1^R \cup s_2^R$

$s$$((s^R)^*)$. Reversal can just move through them.

Thus to reverse this $(((a\cup b) \circ (a))^* \cup ((a\cup b) \circ (b))^*)^R$ we simply follow the rules. To reverse the outer union we simply reverse its two components. To reverse this: $((a\cup b) \circ (a))^*$ kleene star, we simply reverse what is inside it $\rightarrow (((a\cup b) \circ (a))^R)^*$. Then to reverse a concatenation, we index and then switch greatest with least. So we start with $((a\cup b) \circ (a))^R$ and get $((a)^R \circ (a\cup b)^R)$. To reverse that single letter, we reach our base case and get $(a)^R \rightarrow (a)$. This process outlined above describes an inductive description of this change.