Décidabilité des langages des grammaires et des automates

Notez qu'il s'agit d'une question liée à l'étude dans un cours de CS dans une université, ce n'est PAS des devoirs et peut être trouvé ici sous l'examen d'automne 20112.

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

Laisser

$\qquad \mathrm{FINITE}_{\mathrm{CFG}} = \{ < \! G \! > \mid G \text{ is a Context Free Grammar with } |\mathcal{L}(G)|<\infty \}$

Prouver que est un langage décidable. $\mathrm{FINITE}_{\mathrm{CFG}}$

et...

Laisser

$\qquad \mathrm{FINITE}_{\mathrm{TM}} = \{ < \! M\!> \mid M \text{ is a Turing Machine with } |\mathcal{L}(M)|<\infty \}$

Prouver que est un langage indécidable. $\mathrm{FINITE}_{\mathrm{TM}}$

Je suis un peu perdu sur la façon de résoudre ces problèmes, mais j'ai quelques idées qui, je pense, peuvent être dans la bonne direction. La première chose que je connais est que le langage , où$A_{\mathrm{REX}}$

$\qquad A_{\mathrm{REX}} = \{ <\! R, w \!> \mid R \text{ is a regular expression with } w \in\mathcal{L}(R)\}$

est un langage décidable (la preuve se trouve dans Theory of Computation de Michael Sipser , p. 168). La même source prouve également qu'une grammaire sans contexte peut être convertie en une expression régulière, et vice versa. Ainsi, , doit également être décidable car il peut être converti en une expression régulière. Ceci, et le fait que A T M est un -decidable, semble être lié à ce problème.$A_{\mathrm{CFG}}$$A_{\mathrm{TM}}$

La seule chose que je peux penser G passe à des machines de Turing pour (après conversion de G à une expression régulière) et A T M . Accepter ensuite si G le fait et rejeter si G ne le fait pas. Comme A T M est indécidable, cela ne se produira jamais. D'une certaine manière, j'ai l'impression de faire une erreur ici, mais je ne suis pas sûr de ce que c'est. Quelqu'un pourrait-il me prêter main forte ici?$A_{\mathrm{REX}}$$A_{\mathrm{TM}}$$A_{\mathrm{TM}}$

1. Convertissez G en forme normale de Chomsky . De cette façon, la seule dérivation vide serait le symbole de départ qui n'apparaît nulle part ailleurs et donc s'il y a une production qui peut éventuellement se générer elle-même, alors la grammaire est infinie. Si une telle production n'existe pas, chaque symbole ne pourra générer qu'un ensemble fini de chaînes, et la grammaire sera alors finie. Donc, construisez un graphique dirigé où chaque production est un nœud et chaque symbole à l'intérieur d'une production est un bord ciblant ce symbole. Si le graphique a un certain cycle, le CFG est infini, sinon il ne l'est pas. Par conséquent, une machine de Turing pour pourrait être construite en faisant exactement cela, puis F $FINITE_{CFG}$ est décidable.$FINITE_{CFG}$

2. Supposons que est décidable. Disons que H est une machine de Turing qui a une chaîne en entrée et lui - même utilise comme une entrée à F I N I T E T M . Si F I N I T E T M renvoie vrai (c'est-à-dire que H n'accepte qu'un langage fini), alors $FINITE_{TM}$$H$$FINITE_{TM}$$FINITE_{TM}$$H$$H$accepte l'entrée, ce qui conduit à une contradiction puisque l'ensemble d'entrée est infini (la longueur de l'entrée est illimitée, donc accepter n'importe quelle chaîne possible comme entrée signifie accepter un ensemble infini de chaînes). Si I T renvoie false (c'est-à-dire quela langue de H est infinie), puis H rejette l'entrée, ce qui signifie quela langue de H est finie car elle n'accepte aucune entrée (c'est-à-dire que sa langue est vide), ce qui conduit à une contradiction aussi. De cette façon, la supposition que H existe conduit à la contradiction, et cette supposition est basée sur la supposition que F I $FINITE_{TM}$$H$$H$$H$$H$ est décidable. Donc, par contradiction, nous avons queFINIT E T M n'est pas décidable.$FINITE_{TM}$$FINITE_{TM}$

La même source prouve également qu'une grammaire sans contexte peut être convertie en une expression régulière, et vice versa.

Je doute vraiment que Sipser affirme que vous avez probablement mal lu ou mal compris. Cela signifierait que les grammaires sans contexte génèrent exactement les mêmes langages que les grammaires linéaires à droite. C'est faux; les grammaires linéaires droites générées sont un sous-ensemble approprié des grammaires sans contexte dp. Cela dit, la façon dont vous avez essayé d'utiliser des langues régulières pour répondre aux questions ne vous mène nulle part.

Comme vous pouvez le voir ci-dessus dans mes preuves, les deux questions sont en effet deux questions très distinctes et sans rapport. Il se trouve qu'ils étaient libellés de la même manière.

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

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

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

Maintenant, tout ce qu'il faut vérifier, ce sont des mots d'une longueur comprise entre $N$ et $2N$. Si un tel mot existe, alors$L$est infini. Il n'est pas trop difficile de voir que cette déclaration est "si et seulement si", donc si vous ne trouvez aucun mot dans cette plage,$L$est fini. L'efficacité ici est bien pire que la réponse de Victor, mais elle enseigne quelque chose sur la structure des LFC.