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

48

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?LL

L:={wL:uv=w for uΣL and vΣ+}

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

corium
la source
1
il y a une faute de frappe dans la définition de votre , modifier s'il vous plaît à corriger. L
Ran G.
2
"Dessin" n'est pas une preuve; vous devez donner un NFA et prouver qu'il accepte le langage.
Raphaël
Je pense que la définition de la langue n'a toujours pas de sens ...
hugomg
2
de toute façon, le langage spécifique est sans importance si la question est "puis-je dessiner un NFA pour prouver qu'il est régulier". @corium, pouvons-nous modifier la question pour refléter la question plus générale: "comment prouver qu'un spécifique est régulier"? L
Ran G.

Réponses:

48

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

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.LL

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

  • 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 .LLLLLLL

A sonné.
la source
4
Il convient également de noter que prouver qu’une langue est finie est suffisant pour montrer qu’elle est régulière. Cela peut être utile, en particulier dans les preuves non constructives par cas.
Patrick87
2
les expressions rationnelles telles que trouvées dans les langages de programmation peuvent faire beaucoup plus que les langages ordinaires. Vous devriez vous limiter aux constructions "classiques".
David Lewis
4
@ DavidLewis: Sur ce site, vous pouvez supposer que par "expression régulière" on entend la notion classique.
Raphaël
@ DavidLewis Je suis d'accord, il faut éviter "regexp" dans le contexte de la théorie pour éviter toute confusion.
Raphaël
Notez que pour chacune des quatre premières puces, vous aurez besoin d'une preuve montrant que votre représentation est bien correcte.
Raphaël
10

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 K et L sont réguliers.X=KX+LKL
  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. N

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

J.-E. Épingle
la source
4

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.

LLLL

L=(ΣL)Σ

LL

Hendrik Jan
la source
1
L
@ Raphaël Désolé, je me suis fait comprendre. Les réponses précédentes semblent expliquer que nous pouvons construire une description du langage (en tant qu'automate, opérations, etc.). Je suis d'accord. Cependant, la question semble concerner les propriétés de fermeture, voir l'exemple donné. Ce point me manque dans les autres réponses: pour prouver une propriété de fermeture, supposez que vous avez une description et en construisez une nouvelle.
Hendrik Jan
1
L
1
LLLLLLLLL
1
Ah d'accord. En fait, je préférerais éditer la question et supprimer la partie "par exemple", rendant ainsi la question plus générale et une référence pour les questions similaires à venir. ((
Ran G.
4

sks<some property>kk

Rick Decker
la source
4

L1SL2={x1y1xnynΣ:x1xnL1,y1ynL2}
Ai=Σ,Qi,Fi,δi,q0iLii=1,2Σ,Q,F,δ,q0
  • Q1×Q2×{1,2}xiyi
  • q0=q01,q02,1
  • F=F1×F2×{1}
  • δ(q1,q2,1,σ)=δ1(q1,σ),q2,2δ(q1,q2,2,σ)=q1,δ2(q2,σ),1

LR={wR:wΣ}.
(w1wn)R=wnw1LΣ,Q,F,δ,q0Σ,Q,F,δ,q0
  • Q=Q{q0}
  • q0
  • q0
  • δ(q0,ϵ)=FqQσΣδ(q,σ)={q:δ(q,σ)=q}

q0


R(L)={yxΣ:xyL}.
LΣ,Q,F,δ,q0Σ,Q,F,δ,q0q=δ(q0,x)δ(q,y)Fδ(q0,x)=qyx
  • Q={q0}Q×Q×{1,2}q0q,qcurr,sqqcurrsyx
  • F={q,q,2:qQ}δ(q0,x)=q
  • δ(q0,ϵ)={q,q,1:qQ}q
  • δ(q,qcurr,s,σ)=q,δ(qcurr,σ),sq,qcurrQs{1,2}
  • δ(q,qf,1,ϵ)=q,q0,2qQqfFyxy

Ek(L)={xΣ: there exists yL whose edit distance from x is at most k}.
Σ,Q,F,δ,q0LΣ,Q,F,δ,q0Ek(L)
  • Q=Q×{0,,k}
  • q0=q0,0
  • F=F×{0,,k}
  • q,σ,iδ(q,σ),iδ(q,i,σ)
  • q,i+1δ(q,i,σ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,ϵ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,τ)q,σ,τ,ii<k
Yuval Filmus
la source
3

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.

Reinierpost
la source
O (1) espace, tu veux dire? En tout état de cause, cela est couvert par le fait que DFA suffit; il peut être intéressant de noter explicitement cette équivalence en termes de programmation.
Raphaël
Oui, c'est juste une perspective différente.
reinierpost
3

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 .

rLLRL

  • ϵR=ϵσR=σR=
  • (r1+r2)R=(r1R+r2R)(r)R=(rR)(r1r2)R=r2Rr1R

(r1r2)R=r2Rr1R(01)R=10rRLR

h:ΣΔrLh(L)σrh(σ)

Yuval Filmus
la source
0

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, ...)

vonbrand
la source
2
C'est déjà mentionné dans la réponse de Ran.
Raphaël