in Books, Doing Books, Reading books in 2014, Theory of Computation

Theory of Computation #1

Theory of Computation: Formal Languages, Automata and Complexity by J. Glenn Brookshear 1989

Intro: theory-of-computation-cover

I haven’t really dove into working with automata therefore I wanted to work through a book about it. I looked around for a more practical approach and found this book. The author states multiple times that he wants to create the connection between theory and practice.

Like always I will skip problems – often because I solved them before or they are just a small derivation from an other problem.

I really liked working through the book. It wasn’t too heavy on theory but still enough to get a basic understanding. It helped me understanding lexical analyzers better and I finally understood different languages. Also the Church-Turing thesis was pretty interesting and seeing that Brainfuck is as powerful as C, Python or JS.

All in all, I liked the book. I think it’s a good introduction into the topic of formal languages and automata. I had a bit of a clue thanks to Mastering Regular Expressions which talks a lot about ways Regex engines work but nonetheless I learned new stuff and especially the programming exercises were great because I wouldn’t have trust myself to do them.

Great book.


Exercise 1.1.1: Design a transition diagram for recognizing arithmetic expressions of arbitrary length that involve positive integers separated by addition, subtraction, multiplication, or division signs.

So we have the following symbols: positive integers (2,5,8,293,99483) and operators (+,-,*,/).

We let’s start with the integer sub-routine. We take a digit as long as it as digit. If we find an operator the digit is complete, also if we find a EOS. In all other cases there’s an error.

Now we can easily integrate the operators. The first symbol has to be an integer. I assume the form:

If it is completed and an operator is found, the operator is read it and this has to be followed by an integer, i.e. digit. And we iterate as long as we hit EOS.

Write a Comment