Fermeture contre le bon quotient avec une langue fixe

13

J'adorerais vraiment votre aide avec les éléments suivants:

Pour tout fixe, je dois décider s'il y a fermeture sous les opérateurs suivants:L2

  1. Ar(L)={xyL2:xyL}

  2. Al(L)={xyL:xyL2} .

Les options pertinentes sont:

  1. Les langues régulières sont fermées sous resp. A_r , pour n'importe quelle langue L_2AlArL2

  2. Pour certaines langues L2 , les langues régulières sont fermées sous Al resp. Ar , et pour certaines langues L2 , les langues régulières ne sont pas fermées sous Al resp. Ar .

Je pensais que la réponse pour (1) devrait être (2), parce que quand je reçois un mot dans wL et w=xy je peux construire un automate qui peut deviner où x transforme en y , mais il doit ensuite vérifier que y appartient à L2 et si ce ne sera pas régulier, comment ferait-il cela?
La réponse est (1).

Que dois-je faire pour analyser correctement ces opérateurs et déterminer si les langues régulières sont fermées sous eux ou non?

Jozef
la source
Qu'est-ce que ? Voulez-vous dire « ne sont pas fermés» dans la deuxième partie de (b)? Qu'est-ce que L ? AL
Alex ten Brink
Vous n'avez toujours pas défini ? L
Gopi
@Gopi est une langue d'entrée. A ( ) est un opérateur sur les langues dans les deux cas. LA()
Lucas Cook
@Gopi: est un paramètre de A , L 2 est fixe. LAL2
Raphael
Oups mon mauvais, comment n'ai-je pas vu ce oO.
Gopi

Réponses:

11

Pour répondre à ces questions, nous devons autoriser tout . Imaginons donc que L 2 soit un langage très complexe (disons un langage indécidable).L2L2


Commençons par la question facile: (question partie 2). Prenez L 2 indécidable et L = { ε } . Ce qui se produit?Al(L)L2L={ε}

(moral: Vérifiez toujours les "extrêmes": vide , L = { ε } et L = Σ ...)LL={ε}L=Σ


Maintenant pour . C'est une excellente question (généralement une question bonus dans Final / Homeworks). En effet, les langues régulières sont fermées sous A r pour toute langue L 2 . Même indécidable L 2 . Cool, non?ArArL2L2

Alors comment construire un automate pour s'il n'y a pas de machine qui accepte L 2 ?Ar(L)L2

Voici la magie de la «pensée abstraite», c'est-à-dire la preuve existentielle . Si quelqu'un nous donne nous pouvons utiliser cette information pour montrer qu'il existe un automate pour résoudre A ( L ) . Maintenant, les détails.L2A(L)

Nous partons de l'automate de (l'appel est D F A L ). Supposons qu'après le traitement de x, nous nous retrouvons dans un état q . Nous devons accepter s'il existe y L 2 telle que si nous continuons de q traitement y , nous finirons dans un état final de D F A L . Il n'y a pas de machine qui puisse nous dire si y est dans L 2 , mais on peut faire de q un état final de D F A A LLDFALxqyL2qyDFALyL2qDFAALsi la condition ci - dessus contient, par exemple, s'il existe un de telle sorte que si l' on commence à q et processus y nous nous retrouvons dans un état final D F A L .yL2qyDFAL

donc pour construire nous examinons chacun des états de D F A L et faisons de chaque état q un état acceptant si nous pouvons prendre un peu y L 2 et ce y nous conduira de q à un état acceptant de D F A L .DFAALDFALqyL2yqDFAL

Donc ok, est infini, et nous n'avons peut-être pas d'ordinateur pour lister tous les mots dans L 2 , mais tout cela n'a pas d'importance ... l'automate ci-dessus est bien défini, même si je ne peux pas le dessiner à vous état par état. La magie.L2L2

A sonné.
la source
On dirait que vous avez publié une réponse au problème lui-même en même temps. :]
Lucas Cook
bien .. ma réponse contient des spoilers .. peut-être que je devrais mettre une alerte spoiler, donc on peut commencer par votre réponse et si cela ne suffit pas - alors obtenez les détails ..
Ran G.
Wow, merveilleuse réponse, très utile. Merci beaucoup Ran!
Jozef
7

Je ne sais pas si vous cherchez une réponse au problème ou non, donc je ne la fournis pas directement. (Je peux si vous le voulez, cependant.)

Tu as demandé:

Que dois-je faire pour analyser correctement ces opérateurs et déterminer si les langues régulières sont fermées sous eux ou non?

Votre approche de départ est bonne. Comme pour toutes les questions théoriques «ouvertes», vous devriez avoir une idée intuitive de la véracité ou non. Habituellement, cela consiste à essayer des exemples (à la fois communs et marginaux) ou à enquêter sur des cas spéciaux (par exemple, si est régulier? Hors contexte?). Pour ce problème, vous devez développer une supposition quant à savoir si vous pouvez construire un automate / regex pour les opérateurs ou non. Après ça:L2

  • Si vous pensez que vous pouvez, vous devez être en mesure de construire cet automate / regex pour une langue d'entrée régulière .L
  • Si vous pensez que vous ne pouvez pas, vous trouverez généralement des exemples de langues et L 2 tels que A x n'est pas fermé.LL2Ax

(et si une approche ne fonctionne pas, vous pouvez toujours essayer l'autre.)


Pour le problème lui-même:

Ces deux sont le bon opérateur de quotient. (Je crois que le quotient gauche implique de laisser le suffixe au lieu du préfixe.) La différence entre les deux est que tandis que A r ( L ) = L / L 2 , où L 2 est fixé dans les deux cas.Al(L)=L2/LAr(L)=L/L2L2

Vous avez une certaine intuition à propos de , alors voici quelque chose à penser pour A l : A l donne une version modifiée de L 2 . Puisque L 2 pourrait être non régulier, est-il possible pour A l de laisser L 2 inchangé? Si oui, alors A l n'est pas régulier dans ce cas. Sinon, nous devrons argumenter que A l rend L 2 régulier dans tous les cas.ArAlAlL2L2AlL2AlAl L2

Lucas Cook
la source