Re: How to write this RE?

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
--

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