I am trying to understand the concept of synchronised DFAs. I have a question where all the states in the DFA after reading that particular word from the alphabet will reach a particular state with the alphabet (A to Z). And I should prove that a language which accepts any random number of alphabet combinations followed by that particular word is either fully accepted by that synchronised DFA or it is not accepted at all.

I know my question might be confusing but maybe someone can explain to me like a idea how should I start because I'm not really sure and confused about how to go about here.


1 Answer 1


A synchronizing word $w$ has the property that there is a single state $q$ of the DFA, such that for every state $s$ it holds that $\delta(s,w)=q$. That is, after reading $w$ you end up in $q$, regardless of where you started.

Now, suppose you read a bunch of letters. You know nothing about them. But you know that after reading them you are going to read a synchornizing word. Where will the automaton be after reading the entire sequence?

Can you take it from there?


Your Answer

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

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