Вычислимость: Является ли язык DFA, которые получают слова четной длины в P?

Question

Я боролся с этим некоторое время и не могу ничего придумать.Любые указатели будут по достоинству оценены.

Проблема в том, что, учитывая язык всех DFA, которые получают только слова четной длины, докажите, находится ли он в P или нет.

У меня естьрассматривал возможность создания машины Тьюринга, которая перебирает данный DFA в чем-то вроде алгоритма BFS / Dijkstra, чтобы найти все пути от начального состояния до принимающего, но не имеет понятия, как обрабатывать циклы?

Спасибо!

Answer 1

Я думаю, что это в P, в худшем случае квадратичный.Каждое состояние DFA может иметь четыре состояния четности

1. unvisited - состояние 0
2. , о котором известно, что оно доступно за нечетное число шагов - состояние 1
3. известно, что достижимо за четное число шагов - состояние 2
4. известно, что достижимо как за нечетное, так и за четное число шагов - состояние 3

Пометить все состояния какне посещая, поместите начальное состояние в очередь (FIFO, приоритет, что угодно), установите его состояние четности равным 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

Если я что-то не замечаю, каждое состояние DFA обрабатывается не более двух раз, каждоевремя проверки не более size детей на необходимые действия.

Answer 2

Казалось бы, для этого нужны только два состояния.

Ваше состояние входа будет пустой строкой, а также будет состоянием принятия. Добавление anythign в строку переместит его в следующее состояние, которое мы можем назвать «нечетным» состоянием, и не сделает его принятым. Добавление еще одной строки возвращает нас к исходному состоянию.

Полагаю, я больше не уверен в терминологии того, находится ли язык в P или нет, поэтому, если бы вы дали мне определение там, я мог бы сказать вам, подходит ли он ему, но это один из самых простых DFA. ...