Regex to Finite Automata

Admin 1
Viewed 2335

How can I convert a regular expression such as:

((e|£|\$)([1-9][0-9]*|0)(,|\$|\.){1}([0-9][0-9]))|(([1-9][0-9]*|0),[0-9][0-9](EUR))|([1-9][0-9]*|0)\$[0-9]{2}

to a finite automata like this:

finite automata like this

finite-automata regex
2 Answers
user_8600990

I won't go through the details but the process might look like this:

  1. Rewrite your regex as a fully-parenthesized formal regular expression. If your regex has no equivalent fully parenthesized formal regular expression, stop; there is no finite automaton.

  2. Use the standard constructive algorithm for proving finite automata are as powerful as (formal) regular expressions to construct a nondeterministic finite automaton which accepts the language described by the (formal) regular expression obtained in step 1.

  3. Optional: determinize the nondeterministic finite automaton obtained in step 2 using e.g. the subset/powerset constructive algorithm used to show deterministic finite automata are as powerful as nondeterministic ones.

  4. Optional: minimize the deterministic finite automaton obtained in step 3 using some standard DFA minimization algorithm.

user_8472690
Related