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

RegularLanguage''''''s are a strict subset of the ContextFreeLanguage''''''s.

Note: RegularLanguage''''''s 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 RegularExpression''''''s used to be the prototype of RegularLanguage''''''s, but today many if not most implementations of RegularExpression''''''s provided by popular programming languages contain extensions that make them not regular.

There is an alternative to the usual '''implementation''' of RegularExpression''''''s as FiniteStateMachine''''''s, 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


See also RegularExpression
----
CategoryLanguage