Comment prouver qu'une langue est régulière?

Il existe de nombreuses méthodes pour prouver qu'une langue n'est pas régulière , mais que dois-je faire pour prouver qu'une langue est régulière?

Par exemple, si on me donne que est régulier, comment puis - je prouver que les éléments suivants L ' est régulière, aussi?$L$$L'$

$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$

Puis-je dessiner un automate fini non déterministe pour le prouver?

Oui, si vous pouvez proposer l'un des éléments suivants:

• automate fini déterministe (DFA),
• automate fini non déterministe (NFA),
• expression régulière ( expression rationnelle de langages formels) ou
• grammaire régulière

pour un langage , alors L est régulier. Il existe plus de modèles équivalents , mais ce qui précède est le plus courant.$L$$L$

Il existe également des propriétés utiles en dehors du monde "informatique". est aussi régulier si$L$

• c'est fini,

• vous pouvez le construire en effectuant certaines opérations sur les langages normaux, et ces opérations sont fermées pour les langages normaux , tels que

  • intersection,
  • complément,
  • homomorphisme,
  • renversement,
  • quotient gauche ou droit,
  • transduction régulière

  et plus , ou

• utilisant le théorème de Myhill – Nerode si le nombre de classes d'équivalence pour est fini.$L$

Dans l'exemple donné, nous avons une (régulière) langage comme base et que vous voulez dire quelque chose au sujet d' un langage L ' dérivé de celui - ci. En suivant la première approche - construire un modèle approprié pour L ′ - nous pouvons supposer quel modèle équivalent pour L nous le souhaitons; cela restera abstrait, bien sûr, puisque L est inconnu. Dans la seconde approche, nous pouvons utiliser L directement et lui appliquer des propriétés de fermeture afin d’arriver à une description de L ′ .$L$$L'$$L'$$L$$L$$L$$L'$

Méthodes élémentaires

1. Automates finis (éventuellement non déterministes, avec des transitions vides).
2. Expressions régulières.
3. Équations linéaires droites (ou gauches, mais pas les deux), comme où K et L sont réguliers.$X = KX + L$$K$$L$
4. Grammaire régulière (type 3).
5. Opérations préservant les langages normaux (opérations booléennes, produit, étoile, mélange aléatoire, morphismes, inverses de morphismes, renversement, etc.)
6. Reconnu par un monoïde fini.

Méthodes logiques (souvent utilisées dans la vérification formelle)

1. Logique de second ordre monadique (théorème de Büchi).
2. Logique temporelle linéaire (théorème de Kamp).
3. Théorème de Rabin (logique monadique du second ordre à deux successeurs). Très puissant.

Méthodes avancées

1. Lemmes pompant sophistiqués. Voir, par exemple,
   [1] J. Jaffe, Un lemme de pompage nécessaire et suffisant pour les langages normaux , Sigact News - SIGACT 10 (1978) 48-49.
   [2] A. Ehrenfeucht, R. Parikh et G. Rozenberg, Pompage de lemmes pour séries régulières, SIAM J. Comput. 10 (1981), 536-541.
   [3] S. Varricchio, Une condition de pompage pour les ensembles réguliers, SIAM J. Comput. 26 (1997) 764-771.

2. Bien quasiment des ordres. Voir
   [4] W. Bucher, A. Ehrenfeucht, D. Haussler, Régulateurs totaux générés par des relations de dérivation, Theor. Comput. Sci. 40 (1985) 131-148.
   [5] M. Kunz, Solutions régulières des inégalités de langue et des quasi-ordres bien .

3. $\mathbb{N}$

4. Méthodes algébriques basées sur les transductions (voir aussi Opérations préservant les langages normaux ).

La réponse de Ran G. donne une liste assez complète des modèles équivalents qui peuvent être utilisés pour spécifier des langages normaux (et la liste continue, automates à deux voies, logique MSO, mais cela est couvert par le lien sous "Modèles plus équivalents" '). Et comme le souligne Raphaël, nous avons besoin d’un argument pour convaincre le public que la représentation choisie est bien correcte.

$\dots$$L$$L'$$L$$L'$

$L'= (\Sigma^* \setminus L) \cdot \Sigma^*$

$L$$L'$

$s$$k$$s$<some property>$k$$k$

$$L_1 \mathop{S} L_2 = \{ x_1y_1 \ldots x_n y_n \in \Sigma^* : x_1 \ldots x_n \in L_1, y_1 \ldots y_n \in L_2 \}$$ $A_i = \langle \Sigma, Q_i, F_i, \delta_i, q_{0i} \rangle$$L_i$$i=1,2$$\langle \Sigma, Q, F, \delta, q_0 \rangle$

• $Q_1 \times Q_2 \times \{1,2\}$$x_i$$y_i$
• $q_0 = \langle q_{01}, q_{02}, 1 \rangle$
• $F = F_1 \times F_2 \times \{1\}$
• $\delta(\langle q_1, q_2, 1 \rangle, \sigma) = \langle \delta_1(q_1,\sigma), q_2, 2 \rangle$$\delta(\langle q_1, q_2, 2 \rangle, \sigma) = \langle q_1, \delta_2(q_2,\sigma), 1 \rangle$

---

$$L^R = \{ w^R : w \in \Sigma^* \}.$$ $(w_1\ldots w_n)^R = w_n \ldots w_1$$L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$

• $Q' = Q \cup \{q'_0\}$
• $q'_0$
• $q_0$
• $\delta'(q'_0,\epsilon) = F$$q \in Q$$\sigma \in \Sigma$$\delta(q', \sigma) = \{ q : \delta(q,\sigma) = q' \}$

$q'_0$

---

$$R(L) = \{ yx \in \Sigma^* : xy \in L \}.$$ $L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$q=\delta(q_0,x)$$\delta(q,y) \in F$$\delta(q_0,x) = q$$y$$x$

• $Q' = \{q'_0\} \cup Q \times Q \times \{1,2\}$$q'_0$$\langle q,q_{curr}, s \rangle$$q$$q_{curr}$$s$$y$$x$
• $F' = \{\langle q,q,2 \rangle : q \in Q\}$$\delta(q_0,x)=q$
• $\delta'(q'_0,\epsilon) = \{\langle q,q,1 \rangle : q \in Q\}$$q$
• $\delta'(\langle q,q_{curr},s \rangle, \sigma) = \langle q,\delta(q_{curr},\sigma),s \rangle$$q,q_{curr} \in Q$$s \in \{1,2\}$
• $\delta'(\langle q,q_f,1 \rangle, \epsilon) = \langle q,q_0,2 \rangle$$q \in Q$$q_f \in F$$y$$x$$y$

---

$$E_k(L) = \{ x \in \Sigma^* : \text{ there exists $y \in L$ whose edit distance from $x$ is at most $k$} \}.$$ $\langle \Sigma, Q, F, \delta, q_0 \rangle$$L$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$E_k(L)$

• $Q' = Q \times \{0,\ldots,k\}$
• $q'_0 = \langle q_0,0 \rangle$
• $F' = F \times \{0,\ldots,k\}$
• $q,\sigma,i$$\langle \delta(q,\sigma), i \rangle \in \delta'(\langle q,i \rangle, \sigma)$
• $\langle q,i+1 \rangle \in \delta'(\langle q,i \rangle, \sigma)$$q,\sigma,i$$i < k$
• $\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \epsilon)$$q,\sigma,i$$i < k$
• $\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \tau)$$q,\sigma,\tau,i$$i < k$

Une langue est régulière ssi vous pouvez écrire un scanner qui décide sur des chaînes arbitraires ou non ils appartiennent à la langue en utilisant plus d'un fixe quantité de mémoire - la reconnaissance par exemple peut être fait en O (1) l' espace.

La transformation d' une expression régulière est un moyen de prouver la fermeture dans certaines opérations. Les deux exemples les plus simples sont la fermeture sous inversion et la fermeture sous homomorphisme .

$r$$L$$L^R$$L$

• $\epsilon^R = \epsilon$$\sigma^R = \sigma$$\emptyset^R = \emptyset$
• $(r_1+r_2)^R = (r_1^R + r_2^R)$$(r^*)^R = (r^R)^*$$(r_1r_2)^R = r_2^R r_1^R$

$(r_1r_2)^R = r_2^R r_1^R$$(0^*1^*)^R = 1^*0^*$$r^R$$L^R$

$h\colon \Sigma \to \Delta^*$$r$$L$$h(L)$$\sigma$$r$$h(\sigma)$

Une autre méthode consiste à créer le langage à l'aide d'opérations sous lesquelles vous savez qu'elles sont fermées. Ceci est une extension de l'affichage d'une expression régulière, car vous avez beaucoup plus d'opérations disponibles (inverser la chaîne, compléter, intersection, couper un morceau, ne garder qu'une partie, homomorphismes et homomorphismes inverses, ...)