Results 1 to 2 of 2

Math Help - Constructing a deterministic finite automata - using Thompson's contruction

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    4

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

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

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

    Constructing a deterministic finite automata - using Thompson's contruction-automaton1.png

    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.
    Attached Thumbnails Attached Thumbnails Constructing a deterministic finite automata - using Thompson's contruction-automaton1.png  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 26th 2011, 11:53 AM
  2. Finite Automata limitations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 6th 2010, 09:57 AM
  3. Finite Automata question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: July 7th 2009, 02:33 PM
  4. Finite Automata Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 25th 2008, 08:52 AM
  5. Questions relating to Sigma & Finite Automata
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2008, 10:21 AM

Search Tags


/mathhelpforum @mathhelpforum