generalized regular expression
Recall that a regular expression over an alphabet is a finite strings of symbols that are elements of , together with symbols , , , , as well as and , which is put together based on a set of expression formation rules. In a generalized regular expression, additional symbols and are tossed in also. Formally,
any regular expression is in ,
if , then .
An element of is called a generalized regular expression over .
Like regular expressions, every generalized regular expressions are designed to represent languages (it is clear that and are intended to mean set-theoretic intersection and complementation). If is a generalized regular expression:
if is regular expression, then the language represented by as a generalized regular expression is , the language represented by as a regular expression;
if is represented by and is represented by , then is represented by
if is represented by , then is represented by .
By induction, it is easy to see that, given a generalized regular expression , there is exactly one language represented by . We denote the language represented by , and the family of languages represented by generalized regular expressions.
Since regular languages are closed under intersection and complementation, generalized regular expressions in this regard are no powerful than regular expressions. The symbols and are therefore extraneous. In other words,
where is the family of regular languages.
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Title||generalized regular expression|
|Date of creation||2013-03-22 19:01:34|
|Last modified on||2013-03-22 19:01:34|
|Last modified by||CWoo (3771)|