Décidabilité des langues de Grammars et Automata

Question

Notez ceci est une question liée à l'étude dans un cours CS dans une université, il n'est pas devoirs et peut être trouvé ici en automne 2011 exam2.

Voici les deux questions que je suis à la recherche d'un examen passé. Ils semblent être liés, le premier:

  

Soit

     

$ \ qquad \ mathrm {FINI} _ {\ mathrm {CFG}} = \ {<\! G \! > \ Mid G texte de {est un contexte libre avec grammaire} | \ mathcal {L} (G) | <\ infty \} $

     

Montrer que $ \ mathrm {FINI} _ {\ mathrm {CFG}} $ est un langage décidable.

et ...

  

Soit

     

$ \ qquad \ mathrm {FINI} _ {\ mathrm {TM}} = \ {<\! ! M \> \ mid M \ texte {est une machine de Turing avec} | \ mathcal {L} (M) | <\ infty \} $

     

Montrer que $ \ mathrm {FINI} _ {\ mathrm {TM}} $ est une langue indécidable.

Je suis un peu perdu sur la façon de faire face à ces problèmes, mais j'ai quelques idées que je pense peut-être dans la bonne direction. La première chose est que je suis au courant est que la langue $ A _ {\ mathrm {REX}} $, où

  

$ \ qquad A _ {\ mathrm {REX}} = \ {<\! R, w \!> \ Mid R \ texte {est une expression régulière avec} w \ in \ mathcal {L} (R) \} $

est un langage décidable (la preuve est Michael Sipser Théorie de calcul , p. 168). La même source révèle également qu'un contexte grammaire libre peut être converti en une expression régulière, et vice versa. Ainsi $ A _ {\ mathrm {CFG}} $, doit également être décidable car il peut être converti en une expression régulière. Ceci, et le fait que $ A _ {\ mathrm {TM}} $ est un -decidable, semble être lié à ce problème.

La seule chose que je peux penser est le passage G aux machines de Turing pour $ A _ {\ mathrm {REX}} $ (après conversion G à une expression régulière) et $ A _ {\ mathrm {TM}} $. Puis accepter si G fait et le rejet si G ne fonctionne pas. Comme $ A _ {\ mathrm {TM}} $ est indécidable, cela ne se produira jamais. D'une certaine façon, je me sens comme si je fais une erreur, mais je ne suis pas sûr de ce qu'il est. Quelqu'un pourrait-il me prêter s'il vous plaît un coup de main?

Answer 1

1. Convertir G forme normale de Chomsky. De cette façon, la seule dérivation vide serait le symbole de départ qui ne semble nulle part ailleurs et donc s'il y a une production qui peut éventuellement en mesure de générer lui-même, puis la grammaire est infinie. Si aucune production existe, chaque symbole ne sera en mesure de générer un ensemble fini de chaînes, puis la grammaire est finie. Ainsi, construire un graphe orienté où chaque production est un noeud et chaque symbole à l'intérieur d'une production est une arête de ciblage qui symbole. Si le graphique a un certain cycle, le CFG est infini, sinon ce n'est pas. Par conséquent, une machine de Turing pour $ {FINITE_ CFG} $ pourrait être construit exactement ce que fait, puis FINITE_ $ {CFG} $ est décidable.

2. Supposons que $ FINITE_ {TM} $ est décidable. Disons que $ H $ est une machine de Turing qui a une chaîne en entrée et utilise lui-même comme une entrée à $ {FINITE_ TM} $. Si $ FINITE_ {TM} retourne $ true (c.-à-$ H $ accepte seulement une langue finie), puis $ H $ accepte l'entrée, ce qui conduit à une contradiction puisque l'ensemble d'entrée est infinie (la longueur de l'entrée est sans bornes, donc accepter toute chaîne possible que des moyens d'entrée acceptant un ensemble de chaînes infinies). Si $ FINITE_ {TM} $ renvoie false (ie $ H $ 'langue s est infini), alors $ H $ rejette l'entrée, ce qui signifie que $ H $' langue s est finie parce qu'il n'accepte aucune entrée (sa langue est vide), ce qui conduit à une contradiction aussi. De cette façon, la supposition qui existe $ H $ conduit à la contradiction, et cette supposition est basée dans la supposition que $ FINITE_ {TM} $ est décidable. Ainsi, en contradiction, nous avons que $ FINITE_ {TM} $ n'est pas décidable.

  

La même source révèle également qu'un contexte grammaire libre peut être converti en une expression régulière, et vice versa.

Je doute vraiment que Sipser énoncerait que vous avez probablement mal interprété ou mal compris. Cela signifierait que les grammaires contexte génèrent exactement les mêmes que langauges linéaires droit grammaires. C'est faux; les grammaires droite linéaire générer sont un sous-ensemble des langues grammaires hors contexte Dp. Cela dit, la façon dont vous avez essayé d'utiliser les langues régulières pour répondre aux questions que vous ne mène nulle part.

Comme vous pouvez le voir ci-dessus dans mes preuves, les deux questions sont en effet deux questions sans rapport, bien distinctes. Il se trouve qu'ils ont été rédigés de la même.

Answer 2

Une autre façon de décider FINITE_ $ {} $ CFG est par le lemme de pompage.

Le lemme de pompage dit que chaque CFL $ L $ a un certain nombre $ N $ (qui peut être calculée à partir de la grammaire, ou au moins une limite supérieure de celle-ci peut facilement être calculée), de telle sorte que tout $ x \ in L $, ce qui est plus de $ N $ peut être "pompés".

Cela signifie que si $ L $ est fini, tous les mots $ L $ sont plus courtes que $ N $.

Maintenant, tout ce dont on a besoin est de vérifier les mots avec des longueurs entre $ N $ et 2N $ $. Si un tel mot existe, $ L $ est infini. Il est pas trop difficile de voir que cette déclaration est « si et seulement si », donc si vous trouvez pas un mot withing cette plage, $ L $ est fini. L'efficacité ici est bien pire que la réponse de Victor, mais il enseigne quelque chose sur la structure des lampes fluorescentes compactes.