Results 1 to 4 of 4

Math Help - convert regular expression in NFA then in DFA

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    4

    convert regular expression in NFA then in DFA

    I need help how to convert regular expression in NFA then with using transition table I need to convert in DFA. If someone know how, please help me.regular expression is (X+Z*)* ZX*(ZY*+X)*
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: convert regular expression in NFA then in DFA

    Do you have any sources that describe the process? It is described, for example, in "Elements of the Theory of Computation" by Lewis and Papadimitriou and "Introduction to the Theory of Computation" by Sipser. It would be too long to describe the whole thing here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    4

    Re: convert regular expression in NFA then in DFA

    I know to draw NFA for this expression, but I have problem with transition table with which I converted NFA in DFA. I check the solution with JFLAP but my DFA is diffrent from DFA which is produce by JFLAP for this regular expression. I made some mistake in transition table. If you know help me. Please it is really important
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: convert regular expression in NFA then in DFA

    I think I can draw an equivalent DFA, but from common sense, not a formal transformation.

    How do you suggest I can help? There are numerous variations in representing automata (diagrams, one-dimensional state transition tables, two-dimensional tables) and, more importantly, in conversion algorithms. In addition, converting to DFA may explode the number of states. Because of all this, it is probably almost impossible for us to do conversion independently and for our results to coincide even if the resulting automata are equivalent. Maybe you can post your work to be checked.

    Quote Originally Posted by krist
    I need help how to convert regular expression in NFA then with using transition table I need to convert in DFA.
    What do you mean by using transition table for conversion? A transition table is just a representation of an automaton.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Convert Expression from One Form to Another
    Posted in the Algebra Forum
    Replies: 5
    Last Post: January 10th 2012, 03:06 PM
  2. Proof check: Convert DFA into Regular Expression
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 28th 2011, 08:29 PM
  3. Regular expression
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: March 20th 2010, 02:26 PM
  4. regular expression
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: March 16th 2010, 01:30 AM
  5. The name of Regular Expression
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2008, 04:50 PM

Search Tags


/mathhelpforum @mathhelpforum