16 Aug 1996 11:34:28 -0400

Related articles |
---|

How to write this RE? sc7099011@ntuvax.ntu.ac.sg (Johnny Wong) (1996-08-11) |

Re: How to write this RE? fjh@mundook.cs.mu.OZ.AU (1996-08-13) |

Re: How to write this RE? eadengle@dino.uwaterloo.ca (1996-08-13) |

Re: How to write this RE? rwatson@CAM.ORG (Richard Edward Watson) (1996-08-15) |

Re: How to write this RE? bart@time.cirl.uoregon.edu (1996-08-16) |

Re: How to write this RE? torbenm@diku.dk (1996-08-16) |

Re: How to write this RE? bromage@cs.mu.OZ.AU (1996-08-19) |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 16 Aug 1996 11:34:28 -0400 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 96-08-034 |

Keywords: | lex |

Johnny Wong <sc7099011@ntuvax.ntu.ac.sg> writes:

*> I'm am currently in my final year in University and have taken*

*>Compiler Design as one of the electives. I encountered this question in the*

*>Aho book which states:*

*> Give the regular definitions for the following language:*

*> All strings of digits with no repeated digits.*

As a regular expression:

0 | 1 | 2 | ... | 9 | 01 | 02 | ... 09 | 10 | 12 | ...

| 0123456789 | ... | 9876543210

I.e., just list all the (finite number of) possibilities. You would

have no chance of writing this down completely, though.

It is shorter as a DFA: just use a state for each non-empty subset of

digits. A state has a transition for each digit in the set, which goes

to the state representing the set with that digit removed. All states

are accepting. The initial state corresponds to the set of all

digits. This is still quite large, as the number of non-empty sets of

digits is 1023. I don't think using an NFA would help.

Torben Mogensen (torbenm@diku.dk)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.