Comment montrer qu'une langue régulière «inversée» est régulière

Je suis coincé sur la question suivante:

"Les langages réguliers sont précisément ceux acceptés par les automates finis. Étant donné ce fait, montrez que si le langage est accepté par un automate fini, alors est également accepté par un certain fini; compose de tous les mots de inversé. "$L$$L^{R}$$L^{R}$$L$

Donc, étant donné un langage régulier , nous savons (essentiellement par définition) qu'il est accepté par certains automates finis, il y a donc un ensemble fini d'états avec des transitions appropriées qui nous amènent de l'état de départ à l'état d'acceptation si et seulement si l'entrée est une chaîne en L . On peut même insister sur le fait qu'il n'y a qu'un seul État acceptant, pour simplifier les choses. Pour accepter le langage inverse, tout ce que nous devons faire est d'inverser le sens des transitions, de changer l'état de départ en état d'acceptation et l'état d'acceptation en état de départ. Ensuite , nous avons une machine qui est « en arrière » par rapport à l'original, et accepte la langue L R .$L$$L$$L^{R}$

Vous devez montrer que vous pouvez toujours construire un automate fini qui accepte des chaînes dans $L^R$ donné un automate fini qui accepte des chaînes en $L$ . Voici une procédure pour le faire.

1. Inversez tous les liens dans l'automate
2. Ajouter un nouvel état (appelez-le $q_s$ )
3. Dessinez un lien étiqueté avec $\epsilon$ de l'état $q_s$ à chaque état final
4. Transformez tous les états finaux en états normaux
5. Transformez l'état initial en un état final
6. Faire de $q_s$ l'état initial

Formalisons tout cela; nous commençons par énoncer le théorème.

Théorème. Si $L$ est une langue régulière, alors $L^{R}$ .

Soit $A = (Q_A, \Sigma_A, \delta_A, q_A, F_A)$ un NFA et soit $L = L(A)$ . Le $\epsilon$ -NFA $A^{R}$ défini ci - dessous accepte la langue $L^{R}$ .

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

Preuve. Tout d'abord, nous prouvons l'énoncé suivant: $\exists$ un chemin de $q$ à $p$ dans $A$ étiqueté avec $w$ si et seulement si $\exists$ un chemin de $p$ à $q$ dans $A^R$ étiqueté avec $w^R$ (l'inverse de $w$ ) pour $q, p \in Q_A$ . La preuve est par induction sur la longueur de $w$ .

1. Cas de base: $|w| = 1$
   Contient par définition de $\delta_{A^R}$
2. Induction: supposons que l'instruction soit vraie pour les mots de longueur $\lt n$ et let $|w| = n$ et $w = xa$
   Soit $p \in \delta_A^*(q, w) = \delta_A^*(q, xa)$
   Nous savons que $\delta_A^*(q, xa) = \cup_{p'}\delta_A(p', a)$ $\forall p' \in \delta_A^*(q, x)$
   $x$ et$a$ sont des mots de moins de$n$ symboles. Par l'hypothèse d'induction,$p' \in \delta_{A^R}(p, a)$ et$q \in \delta_{A^R}^*(p', x^R)$ . Cela implique que$q \in \delta_{A^R}^*(p, ax^R) \iff p \in \delta_A^*(q, xa)$ .

Laisser $q = q_A$ et $p = s$ pour certains $s \in F_A$ et en remplaçant $w^R$ pour $ax^R$ garantit que $q \in \delta_{A^R}^*(s, w^R)$ $\forall s \in F_A$ . Puisqu'il y a un chemin étiqueté avec $\epsilon$ de $q_s$ à chaque état dans $F_A$ (3. dans la définition de $A^R$) Et un trajet à partir de chaque état $F_A$ à l'état $q_A$ marqué avec $w^R$ , alors il existe un chemin marqué avec $\epsilon w^R = w^R$ de $q_s$ à $q_A$ . Cela prouve le théorème.

Notez que cela prouve que $(L^R)^R = L$ également.

Veuillez modifier s'il y a des erreurs de formatage ou des défauts dans ma preuve ....

Pour ajouter aux transformations à base d' automates décrits ci - dessus, vous pouvez également prouver que les langues régulières sont fermées sous l' inversion en montrant comment convertir une expression régulière pour dans une expression régulière pour L R . Pour ce faire, nous allons définir une fonction R E V sur les expressions régulières qui accepte en entrée une expression régulière R pour un langage L , produit alors une expression régulière R ' pour la langue L R . Ceci est défini de manière inductive sur la structure des expressions régulières:$L$$L^R$$REV$$R$$L$$R'$$L^R$

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

You can formally prove this construction correct as an exercise.

Hope this helps!

Using regular expressions, prove that if $L$ is a regular language then the \emph{reversal} of $L$, $L^R=\{w^R: w\in L\}$, is also regular. In particular, given a regular expression that describes $L$, show by induction how to convert it into a regular expression that describes $L^R$. Your proof should not make recourse to NFAs.

We will assume that we are given a regular expression that describes $L$. Let us first look at the concatination operator ($\circ$), and then we can move onto more advanced operators. So our cases of concatenation deal with the length of what is being concatenated. So first we will break all concatenations from $ab$ to $a\circ b$. When dealing with these break the components up as much as possible: $(ab \cup a)b \rightarrow (ab \cup a) \circ b$, but you cannot break associative order between different comprehensions of course.

$\emptyset^R \rightarrow \emptyset$

$s = \epsilon$

$s$$s \in \Sigma$$s$

$s = \sigma$$\sigma^R$

$s = (\sigma_0\sigma_1...\sigma_{k-1}\sigma_k)$ where k is odd, we have a regular expression which can be written as $(\sigma_0\circ\sigma_1...\sigma_{k-1}\circ\sigma_k)$. The reversal of these even length strings is simple. Merely switch the 0 index with the k index. Then Switch the 1 index with k-1 index. Continue till the each element was switched once. Thus the last element is now the first in the reg ex, and the first is the last. The second to last is the second and the second is the second to last. Thus we have a reversed reg ex which will accept the reversed string (first letter is the last etc.) And of course we reverse each constituent. Thus we would get $(\sigma_k^R\sigma_{k-1}^R...\sigma_{1}^R\sigma_0^R)$

When $s = (\sigma_0\sigma_1...\sigma_{k/2}...\sigma_{k-1}\sigma_k)$ where k is even, we have a regular expression generally which can be written as $(\sigma_0\circ\sigma_1...\sigma_{k-1}\circ\sigma_k)$. The reversal of these even length strings is simple. Merely switch the 0 index with the k index. Then Switch the 1 index with k-1 index. Continue till the each element was switched once, but the k/2 element (an integer because k is even). Thus the last element is now the first in the reg ex, and the first is the last. The second to last is the second and the second is the second to last. Thus we have a reversed reg ex which will accept the reversed string (first letter is the last etc.). And that middle letter. And of course we reverse each constituent. Thus we would get $(\sigma_k^R\sigma_{k-1}^R...\sigma_{k/2}^R...\sigma_{1}^R\sigma_0^R)$

Okay the hard part is done. Let us look to the $\cup$ operator. This is merely a union of sets. So given two strings, $s_1, s_2$, the reverse of $s_1 \cup s_2$ is only $s_1^R \cup s_2^R$. The union will not change. And this makes sense. This will only add strings to a set. It does not matter which order they are added to the set, all that matters is that they are.

The kleene star operator is the same. It is merely adding strings to a set, not telling us how we should construt the string persay. So to reverse a kleene star of a string $s$, is only $((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.