# Showing that a Language is regular using a state machine diagram

I'm in my first few weeks of taking a theoretical course at my school and was wondering what is wrong with my answer to this question.

I've been told to show that the language:

L = {x | x has even length and ends with b} over the alphabet {a,b}

Is regular

I know I can prove this by showing a DFA that accepts that language, over that alphabet. I came up with this solution:

(the letters are in color blocks because the background is black and with a transparent image they wouldn't show up on a black background).

https://imgur.com/a/0ZVqpAZ

This seems to work on strings I've tested such as: ab

abbb

ababab

bbaabbababab

etc

However, my textbook provides a solution with 4 states instead of 3, so I'm wondering where I have gone wrong here? Is there a way to easily check what strings wouldn't work for this DFA? It seems trivial to test every string out there, as it would be impossible.

• DFAs aren't in general unique - you can have many DFAs with different numbers of states that recognize the same language. So, just because the textbook gives a different answer doesn't mean that yours is wrong. Can you prove that your answer is correct? Sep 22, 2018 at 18:24
• Yes, by testing a bunch of strings that should accept or reject.
– 0xI
Sep 22, 2018 at 18:51
• @daniel-mroz DFAs are not unique, but minimal DFA's are. Sep 23, 2018 at 16:51

• May I ask you: which book will you suggest someone like me to start studying autumata. Will it be Mathematical foundations of automata theory or ...? Thanks Sep 22, 2018 at 18:34
Note that it is not necessary to use automata to prove that your language is regular. Setting $$A = \{a,b\}$$, the language of words of even length is $$(A^2)^*$$ and the language of words ending with $$b$$ is $$A^*b$$. These two languages are regular and so is their intersection, which is your language $$L$$.
Now, the 3-state DFA you have computed turns out to be the minimal DFA of $$L$$, and hence your answer is correct.