Regular Language

A RegularLanguage is a very restricted kind of language which e.g. can be parsed without a stack. For details see

http://en.wikipedia.org/wiki/Regular_language

RegularLanguages are a strict subset of the ContextFreeLanguage?s.

Note: RegularLanguages are closed under union, intersection and - interestingly - negation. The latter means that it is possible (fairly efficiently even) to compute the regexp that matches exactly those strings that its negated counterpart doesn't match. Sadly only the fewest regexp packages implement this even though it is most useful e.g. to match the end of comments ("begin~(end)*end)")).

The languages defined by RegularExpressions used to be the prototype of RegularLanguages, but today many if not most implementations of RegularExpressions provided by popular programming languages contain extensions that make them not regular.

There is an alternative to the usual implementation of RegularExpressions as FiniteStateMachines, based on derivatives (think Calculus), explored in an early 1960s paper and then largely ignored/forgotten thereafter except by academics bloating their bibliographies.

   "Derivatives of Regular Expressions"
   Janusz A. Brzozowski
   J. Assoc. Comp. Mach.
   Vol. 11, No. 4, pp. 481-494, October 1964

-- AdamBerger & DougMerritt