2
$\begingroup$

L={ | M is a DFA, |w| is even for all w in L(M)}

Meaning we are looking for a Turing Machine or any algorithm that receives a description of a DFA and decides if all the words this DFA accepts are even in there length(length of 0, 2, 4, 6 ..). DFA stands for Deterministic Finite Automata. My proposal is this, check if all the accepting states stand in an odd positition, meaning you can get to them after an odd number of steps.If so accept M otherwise reject.For example 0011 has even length, 0 takes you to state2 0 state3 1 state4 1 state5. because when you start you are already at state 1(Qstart).

My question: is my solution solid, is it right? Does it run in Polynomial time? I think running time is: o(n^2)

$\endgroup$
3
$\begingroup$

Using the product construction, given $M$ you can construct (in linear time) a DFA for the language $L'(M) := L(M) \cap \Sigma(\Sigma\Sigma)^*$. Using DFS/BFS, you can check whether $L'(M)$ is empty or not (you check whether some accepting state is reachable from the initial state) – $L'(M)$ is empty iff $M \in L$. The entire algorithm runs in linear time.

$\endgroup$
  • $\begingroup$ To be quite honest I have to say that I did not fully understand your construction. How to build it and why is it true? $\endgroup$ – Anwar Saiah Jan 16 '18 at 18:04
  • $\begingroup$ The product construction is a standard construction which can be found in textbooks on automata theory. It is the classical way to prove closure under union and intersection. As for why my construction works, it's up to you to figure out. $\endgroup$ – Yuval Filmus Jan 16 '18 at 22:04
2
$\begingroup$

Your solution is insufficient as written:

My proposal is this, check if all the accepting states stand in an odd positition, meaning you can get to them after an odd number of steps.If so accept M otherwise reject.

If there is an accept state at a position you expect a certain distance from the start state, what happens when that accept state has a 3-cycle that leaves it and comes back to it? In your example, it accepts a string of length 4. But then it would also accept a string of length 7.

You might be able to extend your solution to include these cases, similar to an algorithm for 2-colouring a graph.

$\endgroup$
  • $\begingroup$ We simply do not count the cycles.They don't matter. On the other hand if there are more than one path leading to the same accepting state we have to check them all and see that the states order in the path remains good! $\endgroup$ – Anwar Saiah Jan 16 '18 at 17:59
0
$\begingroup$

Given M, construct in o(1) time a DFA M' that accepts all odd length words in M's language, basically a DFA with two states. Construct a product DFA M'' from M and M'. Check if L(M'') is empty, if so accept otherwise reject.

Both construction of M'' and checking if it's language is empty take polynomial time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.