Comment visualiser l'instruction 'les langages réguliers sont fermés sous x, y ...'?

Question

Je suis en train d'étudier DFA/expression régulière, je continue à rencontrer la déclaration

langues régulières sont fermées par union, intersection, etc. complètent

Je comprends la définition de la fermeture, ce qui signifie que lorsque nous appliquons une opération sur un élément de l'ensemble, l'élément résultant doit également être dans l'ensemble.

Cependant, aucune des ressources auxquelles j'ai fait référence n'en a des exemples concrets? Le prouver par l'équation, Quelqu'un pourrait-il m'aider à visualiser la déclaration ci-dessus avec un exemple de regex?

Answer 1

Utilisons l'alphabet {0,1}.

Laissez L la langue régulière contenant toutes les chaînes de longueur 3, {000, 001, 010, 011, 100, 101, 110, 111}; nous pouvons utiliser l'expression régulière '(0 + 1) (0 + 1) (0 + 1)'.

Laissez L la langue régulière contenant toutes les chaînes commençant par 0, {0, 00, 01, 000, 001, 010, 011, & hellip;}; nous pouvons utiliser l'expression régulière '0 (0 + 1) *'. L'union de ces langages contient toutes les chaînes de longueur 3, plus toutes les chaînes commençant par 0. L'opérateur + fait exactement cela, donc on peut écrire '(0 + 1) (0 + 1) (0 + 1) + 0 (0 + 1) * '. (Nous pourrions légèrement simplifier cette expression, mais nous n'en avons pas besoin.)

L'intersection de ces langages contient toutes les chaînes de longueur 3 commençant par 0: '0 (0 + 1) (0 + 1)' .

Le complément de L contient toutes les chaînes de longueur 0, 1, 2 ou ≥4; on peut écrire 'ε + (0 + 1) + (0 + 1) (0 + 1) + (0 + 1) (0 + 1) (0 + 1) (0 + 1) (0 + 1) *' .

Le complément de L contient la chaîne vide, ainsi que toutes les chaînes commençant par 1; nous pouvons écrire 'ε + 1 (0 + 1) *'.

---

Edité pour ajouter: Cela dit, comme certains commentateurs mentionnent plus haut, il est probablement plus facile d'imaginer ce à l'aide de machines à états finis. En particulier, les DFA (automates finis déterministes) sont probablement la voie à suivre.

Voici quelques-DFA représentant L et L :

Nous pouvons compléter/étendre ces DFA, sans changer les langues qu'ils définissent, en ajoutant non -accepter les états que nous allons passer à chaque fois qu'il n'y a pas d'autres te transition. (De cette façon, chaque chaîne finit dans un état.) Cela donne:

Leur union a la croix-produit des états dans les deux DFA; par exemple, il a un état « AD », ce qui signifie « si je suivais la DFA pour L , je serais dans l'état A, et si je suivais la DFA pour L , Je serais dans l'état D. " Les accepter états sont les états correspondant à accepter les états dans soit DFA:

Leur intersection est similaire, sauf que ses états acceptent les états correspondant à accepter les états dans deux DFA:

Bien sûr, nous pouvons simplifier grandement en supprimant tous les Etats qui ne peut jamais conduire à un état accepter:

Les compléments, enfin, sont tout simplement les mêmes DFA, mais avec tous acceptent les états modifiés de non acceptent états et vice versa: