Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

a simple DFA

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer
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

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.

share|cite|improve this answer

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

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.