Concevoir un langage L tel que ni L ni son complément n'aient un sous-ensemble régulier infini?

Question

J'ai un cours sur la théorie des automates, et maintenant nous apprenons le lemme de pompage. Il y a une question d'exercice nous demandant de "concevoir un langage L tel que ni L ni son complément n'aient un sous-ensemble régulier infini?" Mais je ne comprends pas la question. Qu'est-ce qu'un sous-ensemble régulier infini? Comment devrais-je trouver un langage pouvant répondre à cette exigence?

Quelqu'un peut-il faire la lumière sur cette question?

Merci!

Answer 1

Plus précisément, vous devez trouver une langue L afin qu'il n'y ait pas de sous-ensemble de L qui est un langage régulier infini et il n'y a pas sous-ensemble du complément de L qui est un langage régulier infini. Voici un exemple incorrect: L = l'union de a^n et a^n b^n. Puisque a^n est une langue régulière et qu'il s'agit d'un sous-ensemble de L, cela ne fonctionnerait pas pour la réponse.

Pour trouver un L qui répond aux exigences, j'ai trouvé que ce genre de questions sont plus comme des puzzles. Vous essayez certaines choses, vérifiez si elles fonctionnent ou non, et essayez de réfléchir à la raison pour laquelle elles ne résolvent pas le problème. Finalement, vous obtenez votre avis sur la situation et trouver une solution.

Answer 2

Eh bien, un sous-ensemble régulier infini d'un langage est un sous-ensemble qui est infini et régulier. D'accord, ce n'est probablement pas très utile.

Donc "sous-ensemble" est assez clair. Un «sous-ensemble régulier» est celui qui est accepté par un automate fini déterministe (il existe en fait un théorème étonnant dans la théorie des langages qui dit que cette condition est équivalente à une poignée d'autres conditions). Un "ensemble infini" est un ensemble qui n'est pas fini, ou de manière équivalente, un ensemble qui contient un nombre infini d'éléments.

Donc disons qu'un langage L est spécial s'il a un sous-ensemble régulier infini.

Il est de votre devoir de trouver une langue L tel que L et le complément de L ne sont pas spéciaux.

Pour obtenir quelque part avec ce problème, vous devez d'abord passer votre tête autour de cette définition. Prenez quelques exemples de langues de vos notes et de votre texte. Déterminer si elles sont régulières. Si vous en trouvez une qui ne l'est pas, pensez à ce qui ne la rend pas régulière et voyez si vous concevez un langage qui a la propriété que tous ses sous-ensembles infinis ne sont pas réguliers. Ensuite, voyez ce qui se passe quand vous regardez son complément.

Vous devez construire votre intuition, et la seule façon de le faire est de vous salir les mains.