13 Aug 1996 23:47:57 -0400

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.