Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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)
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.