Re: How to write this RE?

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

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