1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Sep 22, 2018 at 18:24
  • $\begingroup$ Yes, by testing a bunch of strings that should accept or reject. $\endgroup$
    – 0xI
    Sep 22, 2018 at 18:51
  • $\begingroup$ @daniel-mroz DFAs are not unique, but minimal DFA's are. $\endgroup$
    – J.-E. Pin
    Sep 23, 2018 at 16:51

2 Answers 2

1
$\begingroup$

Your answer is correct. If the exercise don’t ask the minimal DFA then the response is not unique (you can make well states).

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Mikasa
    Sep 22, 2018 at 18:34
  • $\begingroup$ I really like the book : Elements of Automata theory by Sakarovitch. $\endgroup$
    – Thinking
    Sep 22, 2018 at 21:27
  • $\begingroup$ Thanks for our time +1 $\endgroup$
    – Mikasa
    Sep 25, 2018 at 12:19
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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