I am so confuse to draw DFA to show the languages. Could someone please give me a few examples to show how DFA works?
I need some examples to study DFA, because I am stack on how should I draw DFA.
-
• The set of strings over {a, b} where every a is immediately followed by a b;
-
• The set of strings over {a, b, c} that do not contain the substring aaa;.
-
• The set of strings over {a, b, c} that begin with a, contain exactly two b’s, and end with cc;
-
• The set of strings over {0, 1, · · · , 9}, without leading 0’s, of odd natural numbers
- • (ab*a)*.
- • (ab)*ba
Let me describe how I think about DFAs using your first example, the set $X$ of strings in which every $a$ is immediately followed by a $b$. I pretend that I'm reading a string $s$ and trying to decide whether or not it's in $X$. I also pretend that I have a bad headache and can't remember very much of what I've read. What do I absolutely have to remember in order to decide whether $s\in X$?
Well, as I start reading $s$, as long as I don't encounter an $a$, all I have to remember is "nothing interesting yet"; so if the string were to end now, it would be in $X$.
As soon as I encounter an $a$, though, I have to remember that I just saw an $a$. That has two effects: First, if $s$ were to end right now, after that $a$, it would not be in $X$, because this $a$ isn't immediately followed by $b$ (or by anything at all). Second, if $s$ doesn't end right there, then I need to pay attention to the next symbol. If it's not $b$, then I've seen an $a$ that is not immediately followed by $b$, so $s$ has no chance to be in $X$. In this case, all I have to remember is "definitely not in $X$" --- I can go through the motions of reading $s$ to the end, but nothing I read from this point on can change the decision of "not in $X$."
Finally, if the next symbol after the $a$ is $b$, then $s$ has passed the test so far, but I have to resume watching for $a$'s, just s I did when I first started reading $s$. That is, I can revert to remembering "nothing interesting yet" and proceed as before.
So the upshot of all this is that I just have to remember one of three phrases: "nothing interesting yet", "just saw an $a$", and "definitely not in $X$." Being lazy, I'll abbreviate these as NIY, JSA, and DN. If $s$ ends with me thinking NIY, then $s\in X$; if it ends with me thinking JSA or DN, then $s\notin X$.
Furthermore, there are simple rules for how I update my memory while reading.
If I think NIY, then reading $a$ makes me think JSA, while reading any letter other than $a$ leaves me still thinking NIY.
If I think JSA, then reading $b$ makes me think NIY, while reading any other letter makes me think DN.
If I think DN, then I continue to think DN no matter what I read.
So that's how I would decide whether $s\in X$ by reading $s$ and remembering a very limited amount of information about what I've read so far. This behavior, "read the string from left to right, remember only a finite amount of information, update the information with each letter you read, and make the decision whether $s\in X$ on the basis of what you remember when you finish reading," is essentially the definition of a DFA. The only difference is in terminology, as follows.
The three things that I might remember, NIY, JSA, and DN, are called the "states" of the DFA (rather than "what I remember"). The rules for updating my memory for every letter that I read are called the "transition rules" of the DFA. What I remember before I even start reading, in this example NIY, is called the "initial state". The situations where I decide that $s\in X$, in this example again just NIY, are called the "accepting states", and the situations where I decide that $s\notin X$, in our example JSA and DN, are the "rejecting states".
To summarize, my strategy for deciding whether $s\in X$ can be summarized as the DFA with three states: NIY, JSA, and DN. The initial state is NIY, and this is also the only accepting state. The transition rules are:
NIY, $a$ ----> JSA
NIY, any letter but $a$ ----> NIY
JSA, $b$ ----> NIY
JSA, any letter but $b$ ----> DN
DN, any letter ----> DN.
That takes care of your first example. I'd approach all the others in a similar way. The key question is always "what must I remember, while reading a string, in order to be able to say, at the end, whether the string is in the language?" The characteristic property of regular languages, which makes them recognizable by DFAs, is that the number of facts that I might need to remember is finite. These facts are the states of the desired DFA.