Problem Detail: 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. That is if the current_letter_read >= previous_letter_read then q1 transits to itself. Otherwise, there is no action. 2) If ' ' 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?
Asked By : neerajdorle
Answered By : David Richerby
Your suggestion is to use two states and stay in the first one until the machine reads a character that is strictly before the last one it read. This can’t be right because a DFA can’t test the current character against previous ones. A DFA knows exactly two things: which state it’s in now and what the next character of the input is. Its decision about which state to move to is based only on those two pieces of information and everything from the past is forgotten. 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). That doesn’t directly answer your question but I think you’ve figured out the answer, from your comments. Yes, it’s going to need about 28 states so it’ll have about 28×27=756 arcs so you’ll have to describe it instead of drawing it in full.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18355
