0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ You will not succeed with two states. Try one state per character. $\endgroup$
    – A.Schulz
    Nov 26, 2013 at 8:13
  • $\begingroup$ 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/ $\endgroup$ Nov 26, 2013 at 9:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Schulz
    Nov 26, 2013 at 9:51
  • $\begingroup$ 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. $\endgroup$ Nov 26, 2013 at 13:33
  • 1
    $\begingroup$ Sipsers book "Introduction in the Theory of Computation" is a good starting point $\endgroup$
    – A.Schulz
    Nov 26, 2013 at 15:21

1 Answer 1

1
$\begingroup$

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 28x27=756 arcs so you'll have to describe it instead of drawing it in full.

$\endgroup$

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.