22 Mar 1996 00:43:23 -0500

Related articles |
---|

Non-deter. regular expr. -> deter. regular expr. faase@cs.utwente.nl (1996-03-20) |

Re: Non-deter. regular expr. -> deter. regular expr. leichter@smarts.com (Jerry Leichter) (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. mtimmerm@microstar.com (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. neumann@PSI.Uni-Trier.DE (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. ikastan@alumnae.caltech.edu (1996-03-24) |

Re: Non-deter. regular expr. -> deter. regular exp mark@omnifest.uwm.edu (1996-03-27) |

From: | Jerry Leichter <leichter@smarts.com> |

Newsgroups: | sci.math,comp.compilers,comp.programming |

Date: | 22 Mar 1996 00:43:23 -0500 |

Organization: | System Management ARTS |

References: | 96-03-125 |

Keywords: | DFA, theory |

Frans F.J. Faase wrote:

*> Is it possible to transform any given non-deterministic regular*

*> expression into a deterministic regular expression? I know it is*

*> possible to map each non-deterministic finite state autonama to a*

*> deterministic finite state autonama, but it seems not be possible to*

*> map any (non-)deterministic finte state autonama to a*

*> (non-)deterministic regular expression.*

[examples of what he wants to do]

*> non-deter. | deter.*

*> --------------------------+------------------------*

*> ( a b | a c ) | a ( b | c ) (1)*

*> [ a ] a | a [ a ] (2)*

*> a* a | a+ (3)*

*> [ a | b | c ] a | (a [ a ]) | ( ( b | c ) a ) (4)*

*> ( a | b | c )* a | ( a | ( ( b | c )* a ))* (5)*

The question as posed is meaningless: There is no definition I've ever

seen for a "[non]deterministic" regular expression.

Determinism and non-determinism are descriptions of execution models

for abstract machines. Regular expressions are not abstract machines;

they are compact, recursive descriptions of sets of strings. In this

way, they are like grammars - in fact, they are exactly equivalent to

regular grammars. One could apply notions from the theory of

grammers. For example:

ambiguous non-ambiguous

-------------------------------------

a* a* a*

Ambiguity can be defined in terms of the underlying grammar (which can

be turned into a description in terms of the RE), and it's a

structural property; but all the examples above are

"non-deterministic" only if you choose a particular interpretation of

the RE's as an execution model. This is most obvious in case 2: These

two can only differ if you assume that matching must be done from left

to right. But of course one can as easily define a matcher for RE's

that scans the string from right to left! In that case, would you

switch the two columns?

The same swapping "determinizes" all the examples but (5) - but (5) is

an incorrect transformation, as the right hand side can match the

empty string, while the left hand side cannot. So I don't know what

to make of it.

Note that, just as there's no special reason to describe matching as

left to right, there's no reason to define it as starting at one end

or another. You could easily define a matcher that starts at the

middle of the string and tries to grow outward - going as far as it

can to the right and then to left; to the left and then to the right;

one step each in alternating directions; or what have you. For any

given RE, some of these choices will require non-determinism in the

"obvious" resulting FSM; some won't. (Of course, we know the

non-determinism can always be eliminated.)

Query: The basic construction gives you an NFSM whose size (number of

states) is linear in the size of the input. Converting that DFSM may

cause an exponential blowup in the number of states. (a) Are there

examples where the exponential blowup actually occurs, but would *not*

occur if scanning in some other order were allowed? (b) Are there RE's

whose expression as a DFSM *always* requires an exponential blowup, no

matter what order you allow scanning in? (I'd guess the answer to (b)

is yes. I suppose one might call such an RE "non-deterministic"!)

-- Jerry

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.