# Re: How to write this RE?

## eadengle@dino.uwaterloo.ca (Ed "Cynwrig" Dengler)13 Aug 1996 23:47:57 -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: eadengle@dino.uwaterloo.ca (Ed "Cynwrig" Dengler) Newsgroups: comp.compilers Date: 13 Aug 1996 23:47:57 -0400 Organization: University of Waterloo References: 96-08-034 Keywords: lex

Greetings!

Johnny Wong <sc7099011@ntuvax.ntu.ac.sg> wrote:
> Give the regular definitions for the following language:
> All strings of digits with no repeated digits.

Well, assuming this means no pairwise repetition (ie. no repeated
digits next to each other), if we were to start with a finite
automota, this would be easy:

Let the language be E = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Let set of states S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, s }.
Let the set of transitions T =
T ( x, d ) = y, x in S, y in S-{s}, x != y,
d in E, y is the state corresponding to d
Let the start state be s
Let the set of final states F = S-{s}

Basically, just have states to remember the last digit, and don't
allow a transition that repeats digits.

To make a regular expression is slightly harder. You could perform
the construction from DFA to RE, but this would be extremely ugly. A
better way is try to detect a pattern. Try the ideas that any base
n+1 number which is not the empty string can be written as

K + K? n (K n)* K?

where K is an expression denoting a base n number, the ? denote an
optional part, and * denotes a repeated part. So let us see how this
pattern works:

RE1 = 0 <== base 1, unary
RE2 = RE1 + RE1? 1 (RE1 1)* RE1?
= 0 + 0? 1 (0 1)* 0? <== base 2, binary
RE3 = RE2 + RE2? 1 (RE2 1)* RE2?
= 0+0?1(01)*0? + (0+0?1(01)*0?)? 2 (0+0?11(01)*0? 2)* (0+0?1(01)*0?)?
<== base 3, trinary

and so forth. Very quickly this becomes extremely ugly, but you can
use the recursive definition to save space:

RE10 = RE9 + RE9? 9 (RE9 9)* RE9?

Ed
--

Post a followup to this message