Re: help making regular expression

Helmut Richter wrote:
On Fri, 16 Mar 2007, Patricia Shanahan wrote:

The insight I think have has nothing to do with making the RE short. It
is not something I would even consider writing by hand. I do think the
symmetry of both the language and the natural DFA for it does give a
structure to the RE.

I do not think so. At least it is not obvious how the symmetry of the DFA can be exploited for a simple, or structured by any intuitive understanding, RE. I have once made a RE for the decimal numbers divisible by 3, and the fine symmetry of the 3-state automaton is totally blurred in the RE. If someone is interested (it is in German but you can at least look at the pictures and the result): http://www.lrz-muenchen.de/services/schulung/unterlagen/regul/regul-14.html#publish4.3.2.0.0.0


I didn't claim the structure can be recovered easily from the RE by
looking at it. The RE about as readable as the average 2000+ character
RE. RE seems to me to be the least readable, most structure-hiding
commonly used representation of languages, except when applied in a
limited number of situations that it fits particularly well.

The structure became visible to me in the process of replacing a couple
of states as though converting the DFA to RE. The structure is also
represented in the structure of the program I wrote to write the RE.

Patricia
.

Relevant Pages

  • Re: UML is semi-formal language !!!
    ... Nodes of DFA ... Tokens mark the edges of DFA. ... The 3GL and UML both have semantic meta-models that are unambiguously mappable to each other. ... It seems really tough to argue that what they are using to encode programs isn't a language. ...
    (comp.object)
  • Re: deterministic log(n)-space-bounded turing machines and finite automata
    ... machines accept exactly the same languages than finite automata do? ... DFA can accept that language. ...
    (sci.math)
  • Re: UML is semi-formal language !!!
    ... relation is like between DFA and the language it recognizes. ... Nodes of DFA ... UML is based upon the same underlying set and graph theory as the 3GLs. ... not the formal language they might implement. ...
    (comp.object)
  • Re: The shocking truth about the naturals
    ... to "prove in classical finitary 1st-order logic" creates asymmetry ... I had hoped to appear to be saying the opposite. ... theorem impacts on interpreting the upward theorem in a way that has no converse ... I am trying the definition of a 1st-order language. ...
    (sci.logic)
  • Re: Languages in Europe - Who understands what ?
    ... Neeraj Mathur wrote: ... I understand the grammar clearly. ... there is a lack of symmetry. ... In language, symmetry isn't important; ...
    (sci.lang)