1
$\begingroup$

Is the $L$ = { $<M>$, $M$ is a DFA accepting all strings except finitely many. } decidable ?

I am sort of confused about the question - what exactly does $M$ accept. How are those finitely many strings look like for a particular $DFA$? It is known that $DFA$ accepts infinite number of strings if it accepts at least one string with length $>=k$, where $k$ is the number of states. Does it mean that M doesn't accept any strings of size less then $|k|$ - since this number would be finite ?

I came up with the decider for $L$ call it $I$, which basically checks $M$ on accepting any strings of size less than $k$.
I = “On input $<M>$, where $M$ is a $DFA$:
1. Let $k$ be the number of states of $M$
2. Construct $k$ $DFA's$ denote them $D_i$, where $i$ goes from $0$ to $k-1$, $D_i$ accepts all strings of length exactly $i$
3. Construct a $DFA$ call it $T_i$ such that $L_i(T) = L(M) ∩ L(D_i)$.
4. Test $L_i(T) = ∅$ using the $E_{DFA}$ decider
5. if $E_{DFA} $ accepts for every $T_i$ and $E_{DFA}$ reject on $M$ => accept , otherwise reject.

Is there a simpler way of answering the question ?

$\endgroup$
4
$\begingroup$

It is indeed decidable, but your solution is not quite correct.

To restate the problem, we're given an encoding $\langle M\rangle$ of a DFA $M$, and we want to decide whether accepts every possible string except a very small (finite) number of them. So for each DFA encoding in this language $L$, there's an associated $x_{M} \in \mathbb{N}$ (which we don't know) and $M$ only rejects $x_{M}$ strings.

So for example, a DFA $A$ that accepts everything (i.e. $\Sigma^{\ast}$) would be in $L$, because $x_{A} = 0$, which is definitely a finite number. Similarly if we have a DFA $B$ which rejects the string $a$, but accepts everything else, this would be in $L$ as $x_{B} = 1$, which is also finite.

Right, now to showing that this decidable for every DFA $M$. To do this we need to make a key observation, similar to what you were proposing, but sort of reversed; if a DFA rejects only finitely many strings, they must all have length smaller than $k-1$, where $k$ is the number of states. Why is this true? Suppose that it rejects a string with length greater than $k-1$, then to process this string the DFA must go around a cycle (either a loop or a longer path, or some combination thereof), but if it can go around the cycle once, it can do it twice, or three times, or any number of times. So if there's at least one long rejected string, there must be an infinite number of rejected strings.

Using this, we can see that if it rejects a string of length somewhere between $k$ and $2k$ (a single go around the cycle can use each state at most twice), then it must reject an infinite number of strings.

Finally we can get to our decider:

  • On input $\langle M \rangle$ where $M$ is a DFA:
    1. One by one, enumerate all strings of length $k$ to $2k$.
      1. Simulate $M$ on each string.
      2. If $M$ rejects any tested string, reject.
    2. If $M$ rejects no strings of length between $k$ and $2k$, accept.
$\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.