I was given this question:

Let M = (Q,Σ, δ, q0, F) be a deterministic finite automaton. Assume that r∈Q is a state of M that is different from the start state q0.

Define the language A⊆Σ* to be the language consisting of all strings that are accepted by M and cause M to enter the state r at least once.

Give a precise description (the 5-tuple definition) of a deterministic finite automaton N that accepts the language A.

My question is, wouldn't it be possible to define N as (Q,Σ, δ, q0, F) with F={r}? Unless I am sorely mistaken, it should be able to meet the question's criteria shouldn't it?


1 Answer 1


If it happened that $F \{r\}$, then that would also happen to be a DFA to which you wouldn't have to do anything to answer the question, but it doesn't cover the case where $r \notin F$.

To rephrase the question a little, imagine you have a DFA $M$ that accepts language $L$, and someone picks a random state $r\neq s_{0}$, can you construct a DFA $M'$ that accepts language $L' \subseteq L$ where $s \in L'$ if it's in $L$ and it makes $M$ use state $r$?

Note that you don't get to pick $r$, it's essentially given as part of the input.

Taking it a little beyond your question, the answer is yes, it's possible, the trick is to do something special when you reach $r$.

A slightly more direct hint:

Make a copy of $M$'s states (including accept status), cancel the accept status of any original states, and change the transitions out of $r$ to point to the counterparts in the duplicated set.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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