Regular expression for string of digits with no repeated digits?

Asked 2011-09-24T13:13:24.117

I'm reading through the dragon book and trying to solve an exercise that is stated as follows

Write regular definitions for the following languages:

All strings of digits with no repeated digits. Hint: Try this problem first with a few digits, such as { 0, 1, 2 }.

Despite having tried to solve it for hours, I can't imagine a solution, beside the extremely wordy

d0 -> 0?
d1 -> 1?
d2 -> 2?
d3 -> 3?
d4 -> 4?
d5 -> 5?
d6 -> 6?
d7 -> 7?
d8 -> 8?
d9 -> 9?
d10 -> d0d1d2d3d4d5d6d7d8d9 | d0d1d2d3d4d5d6d7d9d8 | ...

Hence having to write 10! alternatives in d10. Since we shall write this regular definition, I doubt that this is a proper solution. Can you help me please?

regex

Edit Report

2 Answers

Instead of trying to write a definition that only defines what you want, what if you tell it to generate a list of all strings up digits up to 10 digits in length, including duplicates, and then subtract the ones that contain two zeros, two ones... etc.? Would that work?

answered 2011-09-25T03:04:22.027

A regular definition is a sequence of definitions on the form

d1 -> r1

d2 -> r2

...

dn -> rn

Now make the following definitions:

Zero -> 0

One -> Zero (1 Zero)* | (Zero 1)+ | 1 (Zero 1)* | (1 Zero)+

Two -> One (2 One)* | (One 2)+ | 2 (One 2)* | (2 One)+

Three -> Two (3 Two)* | (Two 3)+ | 3 (Two 3)* | (3 Two)+

Four -> Three (4 Three)* | (Three 4)+ | 4 (Three 4)* | (4 Three)+

...

Nine -> Eight (9 Eight)* | (Eight 9)+ | 9 (Eight 9)* | (9 Eight)+

answered 2013-02-23T01:06:41.600

Regular expression for string of digits with no repeated digits?

2 Answers

Your Answer