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 '\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?