# Design a DFA which accepts words with sorted letters

I have just started learning Theory of Computation and have come across a question which I am not able to solve.

The question is as follows:

Design a DFA that reads a word (character strings) and decides whether the letters
of the word are in sorted order.
For example: 'adept' and 'chilly' have their words in sorted order but 'baby' doesn't.


How should I design a DFA for this language?

What I have tried:

I think there must be two states.

1) While the DFA is scanning the word, the state (q1) will transit to itself
if it reads a letter greater than or equal to previous letter read.

q1 transits to itself. Otherwise, there is no action.

2) If '\0' is encountered, then the DFA transits to the final accepting state.


But in DFA is it possible to do so? How should I draw a DFA for this? I got stuck at this point. Am I missing some basic concept that I should know?

• You will not succeed with two states. Try one state per character. Nov 26 '13 at 8:13
• It will then mean I will 28 states (26 states of letters, 1 start state and the other final state when '\0' occurs.. because I have to check for '\0'.. this is what the original question wants).This will be huge automata then with lot and lots of transition arcs.. (each state will have a transition to all the letters greater itself)..Am i right? Is this because DFA does not have a memory? or why/ Nov 26 '13 at 9:37
• The DEA has a lot of states, but the structure is rather simple. A DEA can only memorize a constant number of things by its states. And your DEA has to remember which letter was the last. If you are interested in the minimal number of states (provable) for a language, you have to argue about the number of equivalence classes of its Myhill-Nerode relation. Nov 26 '13 at 9:51
• can you suggest me good resource/book where I can the basics (preferably online).Because I am a beginner and have no one to guide me. Thankyou for your comments. Nov 26 '13 at 13:33
• Sipsers book "Introduction in the Theory of Computation" is a good starting point Nov 26 '13 at 15:21

When designing automata, it's a good idea to think about what each state means. For example, consider the following automaton, with states that I'll unhelpfully call $A$ and $B$. $A$ is the start state and is accepting; $B$ is non-accepting. Whenever the automaton reads a character, it moves to the other state. What does it do? Well, it accepts the empty string because the start state is accepting. If it reads a character, it moves to the non-accepting state $B$; if it reads another one, it moves back to $A$. So, whenever the machine has read an even number of characters, it's in $A$ and, whenever it's read an odd number of characters, it's in $B$. It would, therefore, make much more sense to call the states "even" and "odd" because that's what they represent. Knowing that, you could easily write an automaton that accepts exactly words whose length is, say, equal to  2, mod 3. Or exactly the words equal to 3, 5 or 11, mod 12. Being a bit more clever, you could write an automaton that accepts exactly the strings whose length is equal to 3 mod 5 and also equal to 0 mod 4 (hint: 20 states).