This is way off out there, but; how is one supposed to understand the 'regular' in regular expressions? I've more or less decided that there are basically two interpretations. 1: 'Regular' as in ordinary -which makes little sense. Especially if you're new to regexes, when they seem extraordinarily extraordinary... 2: As in 'regulated' or 'adjustable' or somesuch -which is what I'm leaning towards... I'm just curious, and no search I've done has yet come up with an explanation for this. (Or maybe I just missed it among the 20 gazillion pages describing what they *do*) Or maybe I'm just having trouble understanding the english lanqu.. lingg.. lugga.. ...what you guys speak ;) tia Jon Clausen P.s. Yes this has absolutely *nothing* at all to do with SuSE, so feel free to reply by PM instead of to the list. -- "The box said something about Windows, so I *carefully* put it back on the shelf..."
* Jon Clausen (dsl23212@vip.cybercity.dk) [020604 13:49]:
how is one supposed to understand the 'regular' in regular expressions?
It's a term from computer theory...a regular expression is a string accepted by a particular class of automata. Someone who actually knows something about computer science will hopefully give a better answer. -- -ckm
On Tuesday 04 June 2002 04:59 pm, Christopher Mahmood wrote:
* Jon Clausen (dsl23212@vip.cybercity.dk) [020604 13:49]:
how is one supposed to understand the 'regular' in regular expressions?
It's a term from computer theory...a regular expression is a string accepted by a particular class of automata. Someone who actually knows something about computer science will hopefully give a better answer.
From 'Introduction to Computer Theory' Cohen, 1986, 823 pgs. Part -1 - Automata Theory Background, Languages, Recursive Definitions, Regular Expressions, Finite Automata, Transition Graphs, Kleene's Thereom, Nondeterminism, Finite Automata with Output, Regular Languages, Nonregular Languages, Decidability. See Chapter 4 (pgs. 38-62) - Regular Expressions '..The language defining symbols we are about to create are called regular expressions. We will define the term regular expression itself recursively. The languages that are associated with these regular expressions are called regular languages and are also said to be defined by finite representation.' Example: ab*a Is the Set of all strings of a's and b's that have at least two letters, that begin and end with a's, and that have nothing but b's inside, if anything at all. language (ab*a) = {aa aba abba abbba abbbba .....} Theorem 5 If L is a finite language (a language with only finitely many words), the L can be defined by a regular expression. Proof To make a regular expression that defines the language L, turn all the words in L to boldface type and stick pluses between them. L= {baa abbba bababa} is baa + abba + bababa (note: this line should be in bold type) if L = {aa ab ba bb} The algorithm described above gives the regular expression aa + ab + ba + bb (note: this line should be in bold type) Another regular expression that defines this language is (a + b)(a + b) (Note: this line should be in bold type) so the regular expression need not be unique. The reason this trick only works for finite languages is that infinite language would become a regular expression which is infinitely long, which is forbidden. ... all I can say is that I I took this 400 level course, Theory of Computing, a long time back after returning to college. It was ugly then, and still is... add to this a class in discrete mathematics and you have one great semester. Most of this was conveniently removed from memory a long time back. George -- SuSE 8.0 | Linux 2.4.19-pre9 i686
On Tue, Jun 04, 2002 at 09:29:38PM -0400, George Auch wrote:
Someone who actually knows something about computer science will hopefully give a better answer.
Hmmm... 'better' in this case is certainly debatable ;D
From 'Introduction to Computer Theory' Cohen, 1986, 823 pgs.
<snip>
L= {baa abbba bababa} is baa + abba + bababa (note: this line should be in bold type) if L = {aa ab ba bb}
<snip>
... all I can say is that I I took this 400 level course, Theory of Computing, a long time back after returning to college. It was ugly then, and still is... add to this a class in discrete mathematics and you have one great semester. Most of this was conveniently removed from memory a long time back.
Man, *that* must've freed some memory... ;) In any case, reading through the above, I realized that I'd been looking in the wrong direction. Because what I'm after is a *linguistic* explanation, not a technical one... So searching google for 'regular thesaurus' immediately came up with a number of pages spelling out 'regular'... As *this* bit f.x: Regular - ADJECTIVE: 1. Without imperfections or blemishes, as a line or contour: clean, perfect. See BEAUTIFUL. 2. Occurring quite often: common, everyday, familiar, frequent, routine, widespread. See USUAL. 3. Commonly practiced or used: accustomed, customary, habitual, usual, wonted. See USUAL 4. Having no change or variation: changeless, constant, equable, even, invariable, invariant, same, steady, unchanging, uniform, unvarying. See SAME. 5. Arranged or proceeding in a set, systematized pattern: methodic, methodical, orderly, systematic, systematical. See ABILITY, ORDER. 6. Characterized by or displaying symmetry, especially correspondence in scale or measure: balanced, proportional, proportionate, symmetric, symmetrical. See SAME. -of which 5. is obviously the more applicable of the senses... So unless someone has something to add, I'll just go on thinking that 'regular expressions' are 'ordered expressions', and declare this thread "solved"... :) As for the other interpretations of the word as listed, I'll leave it up to the reader to decide whether regexes could be described as 'beatiful', 'usual', 'changeless', 'symmetric' or ... Thanks for your time Jon
I sure wish I knew what you're talking about. This is not computer language as I always knew it. (I knew Pascal and BASIC, and I would like to learn C, but not if I have to learn the language you have shown below.) --doug At 21:29 06/04/2002 -0400, George Auch wrote:
On Tuesday 04 June 2002 04:59 pm, Christopher Mahmood wrote:
* Jon Clausen (dsl23212@vip.cybercity.dk) [020604 13:49]:
how is one supposed to understand the 'regular' in regular expressions?
It's a term from computer theory...a regular expression is a string accepted by a particular class of automata. Someone who actually knows something about computer science will hopefully give a better answer.
From 'Introduction to Computer Theory' Cohen, 1986, 823 pgs.
Part -1 - Automata Theory Background, Languages, Recursive Definitions, Regular Expressions, Finite Automata, Transition Graphs, Kleene's Thereom, Nondeterminism, Finite Automata with Output, Regular Languages, Nonregular Languages, Decidability.
See Chapter 4 (pgs. 38-62) - Regular Expressions
'..The language defining symbols we are about to create are called regular expressions. We will define the term regular expression itself recursively. The languages that are associated with these regular expressions are called regular languages and are also said to be defined by finite representation.'
Example: ab*a Is the Set of all strings of a's and b's that have at least two letters, that begin and end with a's, and that have nothing but b's inside, if anything at all.
language (ab*a) = {aa aba abba abbba abbbba .....}
Theorem 5 If L is a finite language (a language with only finitely many words), the L can be defined by a regular expression.
Proof To make a regular expression that defines the language L, turn all the words in L to boldface type and stick pluses between them.
L= {baa abbba bababa} is baa + abba + bababa (note: this line should be in bold type) if L = {aa ab ba bb}
The algorithm described above gives the regular expression aa + ab + ba + bb (note: this line should be in bold type)
Another regular expression that defines this language is (a + b)(a + b) (Note: this line should be in bold type) so the regular expression need not be unique.
The reason this trick only works for finite languages is that infinite language would become a regular expression which is infinitely long, which is forbidden.
... all I can say is that I I took this 400 level course, Theory of Computing, a long time back after returning to college. It was ugly then, and still is... add to this a class in discrete mathematics and you have one great semester. Most of this was conveniently removed from memory a long time back.
George
-- SuSE 8.0 | Linux 2.4.19-pre9 i686
-- To unsubscribe send e-mail to suse-linux-e-unsubscribe@suse.com For additional commands send e-mail to suse-linux-e-help@suse.com
Also check the archives at http://lists.suse.com
More specifically, Regular Expressions and Extended Regular Expressions are very well defined in several standards are used by many Unix/Linux utilities, such as grep, awk, perl and more. It is very specific to pattern matching. On 4 Jun 2002 at 13:59, Christopher Mahmood wrote:
It's a term from computer theory...a regular expression is a string accepted by a particular class of automata. Someone who actually knows something about computer science will hopefully give a better answer.
-- Jerry Feldman Enterprise Systems Group Hewlett-Packard Company 200 Forest Street MRO1-3/F1 Marlboro, Ma. 01752 508-467-4315 http://www.testdrive.compaq.com/linux/
participants (5)
-
Christopher Mahmood -
Doug McGarrett -
George Auch -
Jerry Feldman -
Jon Clausen