# What is the language of this DFA?

How would you write the language for this DFA as L(M) = {...}?

I think in English I would say L(M) is defined as {a,b}* ending in b, ba or aa.

-
I don't see what's to stop a string in this language from having consecutive a's. Assuming $q_0$ is the starting state and is the only accepting state, isn't aa in the language? – Gerry Myerson Sep 16 '11 at 5:27
Yes, it is. Thanks for pointing that out. I hope you don't mind if I edit the question. – Louis Sep 16 '11 at 5:30
No, because every word in the language must have an even number of $a$’s. – Brian M. Scott Sep 16 '11 at 5:43

There are two kinds of non-empty word that go from $q_0$ to $q_0$ without passing through $q_0$ again along the way. One is the word $b$, and the other is any word of the form $ab^*a$. Any number of words of these two types can be concatenated in any order, so the language is that given by the regular expression $(b\mid ab^*a)^*$. In terms of sets that’s $\left(\{b\}\cup \{a\}\{b\}^*\{a\}\right)^*$.

If you look closely at this, you’ll see that it can be matched to any word that contains an even number of $a$’s: match any initial $b$’s to $b^*$, then match the first two $a$’s and any $b$’s between them to $ab^*a$, and repeat as needed, matching any trailing $b$’s to $b^*$. Conversely, any word in the language clearly must contain an even number of $a$’s in order to drive the DFA to $q_0$. Thus, the language can be expressed very simply in English: it’s the set of words over $\{a,b\}$ containing an even number of $a$’s.

-
Thank you. I never considered unions. Looks like my English definition is wrong too. I'll go over that subject again. – Louis Sep 16 '11 at 5:54

Its the language of even number of $a$'s.

Remember $0$ $a$'s is still an even number of $a$'s.

-

I will asume like Gerry Myerson that $q_0$ is the starting state and the only accepting state. I think the set of strings with even number of $a$'s is the accepted language of this DFA. The $b$'s will only keep you in the current state and the $a$'s move you to the other state. You are in state $q_0$ if and only if the number of $a$'s is even.

-