Découper un mot de manière non déterministe
Bonjour,
J'essaie de faire un exercice dans lequel je dois répondre à la question suivante:
Soit L un langage.
S'il existe une machine de Turing non déterministe qui reconnait L en temps linéaire, existe-t-il une machine non déterministe qui reconnait L.L en temps linéaire?
Pour moi la réponse est oui.
Il suffit découper le mot de manière non déterministe en temps linéaire (pour moi c'est possible car étant donné un mot u si on me donne un découpage potentiel en deux mots v et w je peux vérifier en temps linéaire si u=v.w ).
Puis de simplement vérifier étant donné le découpage non déterministe u=v.w si v et w sont dans L.
Mais dans la pratique je ne vois pas comment réaliser une machine de Turing réalisant un découpage non déterministe.
De plus est-il vraiment nécessaire de réaliser une machine, est-ce que mon raisonnement suffit comme preuve?
Merci d'avance.
J'essaie de faire un exercice dans lequel je dois répondre à la question suivante:
Soit L un langage.
S'il existe une machine de Turing non déterministe qui reconnait L en temps linéaire, existe-t-il une machine non déterministe qui reconnait L.L en temps linéaire?
Pour moi la réponse est oui.
Il suffit découper le mot de manière non déterministe en temps linéaire (pour moi c'est possible car étant donné un mot u si on me donne un découpage potentiel en deux mots v et w je peux vérifier en temps linéaire si u=v.w ).
Puis de simplement vérifier étant donné le découpage non déterministe u=v.w si v et w sont dans L.
Mais dans la pratique je ne vois pas comment réaliser une machine de Turing réalisant un découpage non déterministe.
De plus est-il vraiment nécessaire de réaliser une machine, est-ce que mon raisonnement suffit comme preuve?
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.