# Re: How to write this RE?

## fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)13 Aug 1996 23:46:48 -0400

From comp.compilers

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)
| List of all articles for this month |

 From: fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) Newsgroups: comp.compilers Date: 13 Aug 1996 23:46:48 -0400 Organization: Comp Sci, University of Melbourne References: 96-08-034 Keywords: lex

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

> Give the regular definitions for the following language:
> All strings of digits with no repeated digits.

Try a recursive approach. Let <N> denote the RE for all non-empty strings of
digits in the range 0..N with no repeated digits. Then

<0> = 0
<N> = (<N-1>(N<N-1>)*N?)|(N(<N-1>N)*(N-1)?) for N > 0

For example,

<1> = (<0>(1<0>)*1?)|(1(<0>1)*<0>?)
= (0(10)*1?)|(1(01)*0?)

and the language "all strings of _binary_ digits with no repeated digits."
is given by `<1>?', i.e. `(0(10)*1?)|(1(01)*0?)'.

Plugging N=9 into the above and expanding should give you an answer for
decimal digits, but the answer will be "somewhat" long -- it's not the
sort of thing I'd want to do by hand ;-)

--
Fergus Henderson <fjh@cs.mu.oz.au>
WWW: <http://www.cs.mu.oz.au/~fjh>
PGP: finger fjh@128.250.37.3
--

Post a followup to this message