Un CFG utilisant un langage nul est-il décidable?

Question

Si j'ai une grammaire sans contexte G telle que le langage de G est nul, est-ce que G est décidable?

Je sais que la réponse est oui, mais j'ai du mal à le prouver. Ma première pensée est de dire qu'il n'y a qu'un seul état, q1, qui est l'état de départ et l'état d'acceptation pour une machine de Turing qui est l'équivalent de G. Cette machine n'acceptera aucune entrée et s'arrêtera immédiatement et acceptera car elle a atteint une acceptation Etat. Est-ce une réponse acceptable ou suis-je loin d'ici?

MODIFIER:

Comme Joel l'a dit ci-dessous, le langage que j'ai décrit accepte toutes les chaînes. Pour contrer cela, je propose une deuxième machine, G '. G 'a 3 états, l'état de départ q1, un état d'acceptation q2 et un état de rejet q3. q1 passe à q3 sur tous les symboles de l'alphabet de G ', tout comme q2. q1 a une transition epsilon vers q2. Par conséquent, si des symboles existent dans la chaîne envoyée à G ', G' rejettera. S'il n'y a pas de symboles, la seule option est de passer la transition epsilon à l'état d'acceptation. Comment ça sonne?

MODIFIER:

Il a été prouvé que la solution ci-dessus accepte le langage L (G ')= {""}.

Answer 1

Comme vous l'avez dit, la réponse est oui.Une preuve générale est le fait que, étant donné un CFG G , vous pouvez facilement (en quelque sorte) construire un TM simule des dérivations en utilisant cette grammaire.Cependant, vous cherchez une brève preuve de la langue vide.(Le fait que vous ayez un CFG dans ce cas n'a pas d'importance.)

Vous êtes sur la bonne voie en ce sens que si vous pouvez construire une TM qui s'arrête toujours pour un langage L donné, alors L est décidable.Cependant, la machine que vous décrivez acceptera en fait chaque chaîne, c'est-à-dire la langue constituée de toutes les chaînes possibles sur l'alphabet.En effet, si l'état de démarrage est également un état d'acceptation, la machine de Turing acceptera immédiatement au démarrage.Il n'a pas besoin de lire la chaîne d'entrée entière (ou une partie de celle-ci) pour accepter.

Pour définir une TM qui n'accepte rien, laissez l'ensemble des états d'acceptation être vide.Pour garantir que votre machine s'arrête toujours, votre fonction de transition peut également être vide.