You are here
Homegeneralized regular expression
Primary tabs
generalized regular expression
Recall that a regular expression over an alphabet $\Sigma$ is a finite strings of symbols that are elements of $\Sigma$, together with symbols $\varnothing$, $\cup$, $\cdot$, ${}^{*}$, as well as $($ and $)$, which is put together based on a set of expression formation rules. In a generalized regular expression, additional symbols $\cap$ and $\neg$ are tossed in also. Formally,
Definition. Given an alphabet $\Sigma$, let $S$ be the set $\{\varnothing,\cup,\cdot,^{*},\cap,\neg,(,)\}$, considered to be disjoint from $\Sigma$. Let $X$ be the smallest subset of $(\Sigma\cup S)^{*}$ containing the following:

any regular expression is in $X$,

if $u,v\in Y$, then $(u\cap v),(\neg u)\in X$.
An element of $X$ is called a generalized regular expression over $\Sigma$.
Like regular expressions, every generalized regular expressions are designed to represent languages (it is clear that $\cap$ and $\neg$ are intended to mean settheoretic intersection and complementation). If $u$ is a generalized regular expression:

if $u$ is regular expression, then the language represented by $u$ as a generalized regular expression is $L(u)$, the language represented by $u$ as a regular expression;

if $A$ is represented by $u$ and $B$ is represented by $v$, then $A\cap B$ is represented by $(u\cap v)$

if $A$ is represented by $u$, then $\Sigma^{*}A$ is represented by $(\neg u)$.
By induction, it is easy to see that, given a generalized regular expression $u$, there is exactly one language represented by $u$. We denote $L(u)$ the language represented by $u$, and $\mathscr{GR}$ 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 $\neg$ and $\cap$ are therefore extraneous. In other words,
$\mathscr{R}=\mathscr{GR},$ 
where $\mathscr{R}$ is the family of regular languages.
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Mathematics Subject Classification
20M35 no label found68Q70 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections