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

Language: $\{w \mid w \in \{ab\}^*\}$

enter image description here

share|cite|improve this question
By the way, writing $\{w\mid w\in \{ab\}^*\}$ seems a complicated way to write $\{ab\}^*$. – Hendrik Jan Nov 8 '12 at 2:38

It has problems in both directions: it doesn’t accept the empty word, which is in the language, and it does accept a lot of words, like $aba$ and $abb$, that aren’t in the language. The first problem is easily fixed: just make $q_0$ an acceptor state. The second requires some more significant changes. The $b$-transition from $q_3$ should go to $q_1$, the garbage state, and the $a$-transition should go to a new non-accepting state $q_4$. Can you then fill in what the two transitions from $q_4$ should be?

Alternatively, you could get rid of $q_3$ and have a $b$-transition from $q_2$ to $q_1$, using only three states altogether.

share|cite|improve this answer
I see. ok..working on fixing it now. – zeqof Nov 8 '12 at 7:15

No it is not correct, your DFA accepts all strings starting with $ab$ and it doesn't accept the empty string.

share|cite|improve this answer

your DFA will only accept string which starts from ab .so to make it work make every state will be a final state.

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.