Como mostrar que um idioma regular “invertido” é regular

Estou preso na seguinte pergunta:

"Linguagens regulares são precisamente aquelas aceitas por autômatos finitos. Dado esse fato, mostre que se a linguagem é aceita por algum autômato finito, então também é aceita por algum finito; consiste em todas as palavras de invertido. "L R L R$L$$L^{R}$$L^{R}$$L$

Portanto, dada uma linguagem regular , sabemos (essencialmente por definição) que ela é aceita por alguns autômatos finitos; portanto, há um conjunto finito de estados com transições apropriadas que nos levam do estado inicial ao estado de aceitação se e somente se a entrada é uma string em . Podemos até insistir que existe apenas um estado de aceitação, para simplificar as coisas. Para aceitar o idioma reverso, tudo o que precisamos fazer é reverter a direção das transições, alterar o estado inicial para um estado de aceitação e o estado de aceitação para o estado inicial. Então nós temos uma máquina que está "atrasada" em comparação com o original e aceita o idioma .L L $L$$L$$L^{R}$

Você tem que mostrar que você sempre pode construir um autômato finito que aceita cadeias em $L^R$ dado um autômato finito que aceita cadeias em $L$ . Aqui está um procedimento para fazer isso.

1. Inverta todos os links no autômato
2. Adicione um novo estado (chame-o de $q_s$ )
3. Desenhe um link rotulado com $\epsilon$ do estado $q_s$ para cada estado final
4. Transforme todos os estados finais em estados normais
5. Transforme o estado inicial em um estado final
6. Tornar $q_s$ o estado inicial

Vamos formalizar tudo isso; começamos declarando o teorema.

Teorema. Se $L$ é uma linguagem regular, então é assim $L^{R}$ .

Seja $A = (Q_A, \Sigma_A, \delta_A, q_A, F_A)$ seja um NFA e seja $L = L(A)$ . O $\epsilon$ -NFA $A^{R}$ definido abaixo aceita a linguagem $L^{R}$ .

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

Prova. Primeiro, provamos a seguinte declaração: $\exists$ um caminho de $q$ a $p$ em $A$ rotulado com $w$ se e somente se $\exists$ um caminho de $p$ a $q$ em $A^R$ rotulado com $w^R$ (o inverso de $w$ ) para $q, p \in Q_A$ . A prova é por indução no comprimento de $w$ .

1. Caso base: $|w| = 1$
   Mantém por definição de $\delta_{A^R}$
2. Indução: assuma que a instrução vale para palavras de comprimento $\lt n$ e deixe $|w| = n$ e $w = xa$
   Seja $p \in \delta_A^*(q, w) = \delta_A^*(q, xa)$
   Sabemos que $\delta_A^*(q, xa) = \cup_{p'}\delta_A(p', a)$ $\forall p' \in \delta_A^*(q, x)$
   $x$ e$a$ são palavras de menos de$n$ símbolos. Por hipótese de indução,$p' \in \delta_{A^R}(p, a)$ e$q \in \delta_{A^R}^*(p', x^R)$ . Isso implica que$q \in \delta_{A^R}^*(p, ax^R) \iff p \in \delta_A^*(q, xa)$ .

Deixando $q = q_A$ e $p = s$ para alguns $s \in F_A$ e substituindo $w^R$ para $ax^R$ garantias que $q \in \delta_{A^R}^*(s, w^R)$ $\forall s \in F_A$ . Como existe um caminho rotulado com $\epsilon$ de $q_s$ para todos os estados em $F_A$ (3. na definição de $A^R$) E um caminho de todos os estados em $F_A$ ao estado $q_A$ marcado com $w^R$ , então existe um caminho marcado com $\epsilon w^R = w^R$ de $q_s$ para $q_A$ . Isso prova o teorema.

Note-se que isto prova que $(L^R)^R = L$ , bem.

Por favor, edite se houver algum erro de formatação ou falha na minha prova ....

Para adicionar às transformações baseada em autômatos descritos acima, você também pode provar que linguagens regulares são fechados sob reversão, mostrando como converter uma expressão regular para em uma expressão regular para L R . Para fazer isso, vamos definir uma função R E V em expressões regulares que aceita como entrada uma expressão regular R em alguma linguagem L , em seguida, produz uma expressão regular R ' para a linguagem L R . Isso é definido indutivamente na estrutura das expressões regulares:$L$$L^R$$REV$$R$$L$$R'$$L^R$

1. $REV(\epsilon) = \epsilon$
2. $REV(\emptyset) = \emptyset$
3. para qualquer 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))$

Você pode provar formalmente essa construção como um exercício correto.

Espero que isto ajude!

Usando expressões regulares, prove que se é uma linguagem regular, a \ emph {reversão} de L , L R = { w R : w ∈ L } também é regular. Em particular, dada uma expressão regular que descreve L , mostrar por indução como convertê-lo em uma expressão regular que descreve L R . Sua prova não deve recorrer aos NFAs. $L$$L$$L^R=\{w^R: w\in L\}$$L$$L^R$

Vamos supor que nos é dada uma expressão regular que descreve . Vamos primeiro olhar para o operador de concatinação ( ∘ ) e depois podemos passar para operadores mais avançados. Portanto, nossos casos de concatenação lidam com a duração do que está sendo concatenado. Então, primeiro, quebraremos todas as concatenações de a b para a ∘ b . Ao lidar com isso, quebre os componentes o máximo possível: ( a b ∪ a ) b → ( a b ∪ a ) ∘ $L$$\circ$$ab$$a\circ b$$(ab \cup a)b \rightarrow (ab \cup a) \circ b$, mas você não pode quebrar a ordem associativa entre diferentes compreensões, é claro.

Quando $\emptyset^R \rightarrow \emptyset$

Quando , temos a string vazia que já está invertida, portanto o mecanismo não muda$s = \epsilon$

Quando é apenas uma letra, como em s ∈ Σ , a reversão é apenas essa letra, $s$$s \in \Sigma$$s$

Quando , temos um único constituinte, então apenas invertemos esse constituinte e, portanto, σ $s = \sigma$$\sigma^R$

Quando , onde k é impar, que tem uma expressão regular que pode ser escrito como ( σ 0 ∘ σ 1 . . . Σ k - 1 ∘ σ k$s = (\sigma_0\sigma_1...\sigma_{k-1}\sigma_k)$$(\sigma_0\circ\sigma_1...\sigma_{k-1}\circ\sigma_k)$. A reversão dessas seqüências de comprimento par é simples. Simplesmente alterne o índice 0 com o índice k. Em seguida, alterne o índice 1 com o índice k-1. Continue até que cada elemento tenha sido trocado uma vez. Assim, o último elemento agora é o primeiro no reg ex, e o primeiro é o último. O penúltimo é o segundo e o segundo é o penúltimo. Assim, temos um reg ex invertido que aceita a string invertida (a primeira letra é a última etc.) E, é claro, invertemos cada constituinte. Assim que teríamos $(\sigma_k^R\sigma_{k-1}^R...\sigma_{1}^R\sigma_0^R)$

$s = (\sigma_0\sigma_1...\sigma_{k/2}...\sigma_{k-1}\sigma_k)$$(\sigma_0\circ\sigma_1...\sigma_{k-1}\circ\sigma_k)$$(\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)^*)$

$(((a\cup b) \circ (a))^* \cup ((a\cup b) \circ (b))^*)^R$$((a\cup b) \circ (a))^*$$\rightarrow (((a\cup b) \circ (a))^R)^*$$((a\cup b) \circ (a))^R$$((a)^R \circ (a\cup b)^R)$$(a)^R \rightarrow (a)$. Este processo descrito acima descreve uma descrição indutiva dessa alteração.