Re: Regualar Expression Theory


"Etienne Marais" <etienne@xxxxxxxxxxxxxxxx;etienne.marais@xxxxxxxxx> wrote
in message news:dpmvjh$go8$1@xxxxxxxxxxxxxxxxxxxxx
> Stephen Harris wrote:
>
>>
>> "Etienne Marais" <etienne@xxxxxxxxxxxxxxxx;etienne.marais@xxxxxxxxx>
>> wrote
>> in message news:dpk444$gpv$1@xxxxxxxxxxxxxxxxxxxxx
>>> Hi
>>>
>>> Could somebody please refer me to
>>> the 'academics' behind regular
>>> expressions ? Different shells
>>> and utilities have different
>>> interpretations. I would like to
>>> know more about where RE's come
>>> from and how they developed...
>>>
>>> --
>>> Etienne Marais
>>> Cosmic Link
>>> South Africa
>>>
>>
>> Papadimitriou and Sispser have written Introductions to the theory of
>> computation.
>> Papadimitriou taught a class in foundational papers which contributed to
>> computation.
>> The most interesting paper to me was: "Simulating physics with computers"
>> http://www.cs.berkeley.edu/%7Erfonseca/courses/classics/feynman.pdf
>>
....
>> On computable numbers, with an application to the Entscheidungsproblem.
>> Alan Turing 1936
>

>> Textbook:
>> H.R. Lewis, C.H. Papadimitriou:
>> Element of the Theory of Computation, Prentice Hall, 2nd Edition, 1998.
>>
>> Reference Books:
>> C. Calude:
>> Theories of Computational Complexity, North Holland, 1988.
>> M. Chandrasekaran, and K.L.P. Mishra:
>> Theory of Computer Science: Automata, Language and Computation,
>> Prentice
>> Hall, 1995.
>> ***J.E. Hopcroft, J.D. Ullman:
>> Introduction to Automata Theory, Languages, and Computation,
>> Addison-Wesley, Massachusetts, 1979.
>> ***M. Sipser:
>> Introduction to the Theory of Computation, Pws Pub Co, USA, 1996.
>> C.H. Smith:
>> A Recursive Introduction to the Theory of Computation, Springer Verlag,
>> 1994.
>> R.G. Taylor:
>> Model of Computation and Formal Languages, Oxford University Press,
>> 1997. M.R. Garey and D. S. Johnson:
>> Computer and Intractability, W.H. Freeman and Company, New York, 1979.
>
> Are these references related to regular expressions ?
>
> --
> Etienne Marais
> Cosmic Link
> South Africa
>

http://www.cs.rochester.edu/u/leblanc/csc173/fa/re.html
equivalences of regular expressions and finite automata
The uniform halting problem is decidable for finite-state automata.

"Could somebody please refer me to
the 'academics' behind regular
expressions ?"

The theory of regular expressions are taught in Intro courses of
Automata, Language and Computation, for example
1.. Tour Of Advanced Topics In Finite Automata
12.1 DFA Minimization
12.2 Two-Way Finite Automata
12.3 Finite-State Transducers
2.. Regular Expressions
13.1 Regular Expressions, Formally Defined
13.2 Regular Expression Examples
3.. Regular Expressions, Regular Languages
14.1 For Every Regular Expression, a Regular Language
14.2 Regular Expressions and Structural Induction
14.3 For Every Regular Language, a Regular Expression
14.4 Regular Languages Again
4.. NFA To Regular Expression
15.1 Internal Languages
15.2 Regular Expressions For Internal Languages
15.3 Completed Construction and Proof
5.. Regular Expression Applications
16.1 The egrep Tool
16.2 Non-Regular Regexps
16.3 Implementing Regexps
16.4 The lex Tool
SH: The foundations of computer science are formal languages,
automata and computability. The reference books are all quite
relevant to Regular Expressions. How many topics you tie into
your understanding depends on the academic depth you desire.
Usually, Discrete Math is required before taking this course.

The recommended papers in the Classics section led to the
creation of computer science, especially, "On computable numbers,
with an application to the Entscheidungsproblem." Alan Turing 1936
Other classic papers depend on the depth of your interest.

Without surrounding background and context, how do you know what

"equivalences of regular expressions and finite automata
The uniform halting problem is decidable for finite-state automata."

means, if you don't know what undecidable means.

http://decsai.ugr.es/~jags/fat.html

Contents
"Introduction to the notion of finite state machines and their use to
recognize strings in a language. Finite deterministic automata (FDA).
Definition of regular languages as those accepted by FDAs. Examples. Finite
non-deterministic automata (FNA). Proof that the class of languages accepted
by FNAs coincides with the regular languages.

Operations on regular languages: finite union and intersection,
concatenation, and Kleene closure. Regular expressions and the regular
languages they denote. Proof that a language is regular if and only if it is
denoted by a regular expression (Kleene's Theorem). The Pumping Lemma.
Examples of languages that are not regular. Minimization of finite automata.
Algorithms."

SH: If you want something academic and specific there are online lecture
notes at: http://www.cs.wm.edu/~wm/CS423/lectures.html

Lecture Notes (1): Forms of theorems, proof techniques, and introduction
to Theory of Compuatation.
Lecture Notes (2): Deterministic and nondeterministic finite automata.
Lecture Notes (3): Regular expressions.
I think you will have difficulty if you are not academically prepared to
understand (background) the "academics behind regular expressions".

Regards, Stephen









.

Relevant Pages

  • Re: Search for multiple things in a string
    ... > language in places. ... > Regular expressions ... None of those state that regular expressions aren't a language. ... readability is a very important part of choosing the best ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Application of formal languages
    ... Regular languages are easy to illustrate, ... How does one catch viruses and spam? ... Example 2 for regular expressions, ... Context-free languages are in some sense the next step up. ...
    (comp.theory)
  • Re: Perl HTML searching
    ... My initial reaction would be something like - I'm pretty sure *any* method, including the use of HTML::LinkExtor, or XML transform, involves using regular expressions "for the purposes of parsing HTML". ... But unless your language is a regular language (and there aren't many ...
    (comp.lang.perl.misc)
  • Re: What do you need to have to be considered a Master at Perl?
    ... Someone who understands the Chomsky hierarchy, ... I don't think perl actually existed back then. ... "I've learnt how to match balanced parentheses with regular expressions." ... I don't care if perl regular expressions are or aren't kosher. ...
    (comp.lang.perl.misc)
  • Re: Perl HTML searching
    ... Read up on perl regular expressions. ... While reading up on regular expressions is certainly a good idea, ... it is a horrid idea for the purposes of parsing HTML. ... Using REs to do _part_ of the work of parsing any language is a ...
    (comp.lang.perl.misc)