Computabilité: La langue des DFA qui reçoivent des mots de longueur égale dans P?

Question

J'ai lutté avec celui-ci pendant un certain temps et ne suis pas capable de trouver quelque chose. Tout pointeur serait vraiment apprécié.

Le problème est le suivant: étant donné la langue de tous les DFA qui ne reçoivent que des mots de longueur égale, vérifiez si elle est en P ou non. J'ai envisagé de faire une machine de gravure qui dépasse le DFA donné dans quelque chose comme l'algorithme de BFS/Dijkstra afin de trouver tous les chemins de l'état de départ à celui qui accepte, mais je ne sais pas comment gérer les boucles.

Merci!

Answer 1

Je pense que c'est en P, au pire en quadratique. Chaque état de la DFA peut avoir quatre parité Etats

1. unvisited - état 0
2. connu pour être accessible à un nombre impair d'étapes - état 1
3. connu pour être accessible à un nombre pair de étapes - état 2
4. connu pour être accessible à la fois, numéros pairs et impairs des étapes - état 3

Marquez tous les états que unvisited, mettre l'état de départ dans une file d'attente (FIFO, priorité, quelle que soit), définissez son état de parité à 2.

child_parity(n) 
    switch(n) 
     case 0: error 
     case 1: return 2 
     case 2: return 1 
     case 3: return 3 

while(queue not empty) 
    dfa_state <- queue 
    step_parity = child_parity(dfa_state.parity_state) 
    for next_state in dfa_state.children 
     old_parity = next_state.parity_state 
     next_state.parity_state |= step_parity 
     if old_parity != next_state.parity_state // we have learnt something new 
      add next_state to queue // remove duplicates if applicable 
for as in accept_states 
    if as.parity_state & 1 == 1 
     return false 
return true 

À moins que je suis sur quelque chose, chaque état DFA est traité deux fois au maximum, chaque fois que la vérification au plus size enfants pour l'action nécessaire.

Answer 2

Il semblerait que cela ne nécessite que deux états.

Votre état d'entrée serait une chaîne vide, et serait également un état d'acceptation. L'ajout de anythign à la chaîne la ferait passer à l'état suivant, que nous pourrions appeler l'état 'impair', et non en faire un état d'acceptation. L'ajout d'une autre chaîne nous ramène à l'état d'origine. Je suppose que je ne suis plus sûr sur la terminologie de savoir si une langue est en P ou non, donc si vous me donniez une définition, je pourrais vous dire si cela correspond, mais c'est l'un des DFA les plus simples environ ...