Re: How to write this RE? (Torben AEgidius Mogensen)
16 Aug 1996 11:34:28 -0400

          From comp.compilers

Related articles
How to write this RE? (Johnny Wong) (1996-08-11)
Re: How to write this RE? (1996-08-13)
Re: How to write this RE? (1996-08-13)
Re: How to write this RE? rwatson@CAM.ORG (Richard Edward Watson) (1996-08-15)
Re: How to write this RE? (1996-08-16)
Re: How to write this RE? (1996-08-16)
Re: How to write this RE? (1996-08-19)
| List of all articles for this month |

From: (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 <> 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 (

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.