13 Aug 1996 23:46:48 -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: | fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) |

Newsgroups: | comp.compilers |

Date: | 13 Aug 1996 23:46:48 -0400 |

Organization: | Comp Sci, University of Melbourne |

References: | 96-08-034 |

Keywords: | lex |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.