Thread: Constructing a deterministic finite automata - using Thompson's contruction

Hi

I need some help with constructing a syntax tree for the following regular expression:

a + ba*

Anyone have any suggestions - websites with a simple example, useful textbooks etc.?

It's quite computer science orientated.

Thanks

It's quite easy to write a DFA right away:



What do you mean by Thompson's construction: a translation from a nondeterministic automaton to a deterministic one? I imagine there are several similar translations, so it is difficult to get exactly the same result unless you provide a detailed description of the construction. Also, what do you mean by a syntax tree?

The books that I found useful in regard to finite automata are Introduction to the Theory of Computation by Sipser and Elements of the Theory of Computation by Lewis and Papadimitriou.