1
$\begingroup$

Can you suggest me a good book with illustrative examples and problems with solutions for finite languages and automata theory?

I tried Hopcroft's but it has mostly theory and not many problems with solutions.

Thanks! :)

$\endgroup$
  • 2
    $\begingroup$ College-level textbooks are usually not a list of solved exercises, like some high school texts are. You will have to adjust. $\endgroup$ – Yuval Filmus May 20 '17 at 10:09
  • 2
    $\begingroup$ Try a few other common textbooks, such as Sipser. $\endgroup$ – Yuval Filmus May 20 '17 at 10:35
2
$\begingroup$

Try this question to get an idea. I think the classical ones at universities are the one from Sipser and Hopcroft's one. For Hopcroft I would really look for the old version if you are mathematically inclined. They removed a lot of proofs in new versions.

For specific examples of problems you'll get solutions here and there over the Internet. It is good not to have a straight look to the solution and having the solution very near can be very tempting at times.

While looking for books to get an idea of what's on them I like this Internet library. Then you can always buy the book on paper or borrow it from your University library.

Hope this helps.

Some books with solutions: (under construction)

Hopcroft's et alii. solutions to their book.

Apparently, Sipser's book contains solutions after each chapter.

$\endgroup$
  • $\begingroup$ I think the OP is looking for a textbook having less proofs and more worked out exercises, somewhat similar to a tutorial compared to a lecture. $\endgroup$ – Yuval Filmus May 20 '17 at 10:46
  • $\begingroup$ @YuvalFilmus I think he won't find that in a single book. The link to the question on theoretical computer science gives a lot of examples... $\endgroup$ – Rodrigo May 20 '17 at 10:51
1
$\begingroup$

Here are some which contains more solved examples :

  1. An Introduction to Formal Languages and Automata by Peter Linz.
  2. Automata and Computability by Dexter C. Kozen.
$\endgroup$
0
$\begingroup$

I know its been a while since this question has been asked, but I think that Problem Solving in Automata, Languages, and Complexity by Ding Zhu Du is the best book for, surprisingly, problem solving!

It contains plentiful examples for DFA, NFA, using pumping lemma to prove irregularity, proving regularity of weird languages which seem to be irregular and complicated!

Its available as PDF for free on internet, I hope it's legal!

$\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.