This means that the additional symbols and in a generalized regular expressions are extraneous: removing them will not affect the representational power of the expressions with respect to regular languages.
What if we remove , the Kleene star symbol, instead? With regard to regular expressions, removing severely limits the power of the expressions. By induction, the represented languages are all finite. In this entry, we briefly discuss what happens when is removed from the generalized regular expressions.
Definition. Let be an alphabet. A language over is said to be star-free if it can be expressed by a generalized regular expression without . In other words, a star-free language is a language that can be obtained by applying the operations of union, concatenation, and complementation to and atomic languages (singleton subsets of ) a finite number of times.
If we denote the family of star-free languages (over some alphabet ), then is the smallest set of languages over such that
for any ,
if , then .
In relations to finite and regular languages, we have the following:
where denotes the family of finite languages over .
Furthermore, it is easy to see that is closed under Boolean operations, so that contains infinite languages, for example represents . As a result, the first inclusion must be strict. This example also shows that languages representable by expressions including the Kleene star may still be star-free. Here’s another example: over the alphabet . This language can be represented as
Is the second inclusion strict? Are there regular languages such that representations by expressions including the Kleene star is inevitable? The following proposition answers the question:
A language is star-free iff there exists a non-negative integer such that, for any words over , iff .
A language satisfying the second statement in the proposition is known as noncounting, so the proposition can be restated as: a language is star-free iff it is noncounting.
As a result of this fact, we see that languages such as is not star-free, although it is regular. Indeed, if we pick as in the statement of the proposition above, we see that is in the language iff is not in the language, for any . Therefore, the second inclusion in chain (1) above is also strict.
The above proposition also strengthens chain (1): denote by the family of locally testable languages, then
The first inclusion is due to the fact that, for any -testable language (over some ), we have
(the definition of is found in the entry on locally testable languages). Note the first inclusion is also strict. For example, the language represented by is star-free but not locally testable.
|Date of creation||2013-03-22 18:59:05|
|Last modified on||2013-03-22 18:59:05|
|Last modified by||CWoo (3771)|