# convert regular expression in NFA then in DFA

• Jun 5th 2012, 06:20 AM
krist
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)*
• Jun 5th 2012, 06:38 AM
emakarov
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.
• Jun 5th 2012, 06:45 AM
krist
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
• Jun 5th 2012, 07:45 AM
emakarov
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.