A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, boolean operators and concatenation but no Kleene star. For instance, the language of words over the alphabet {a,b} that do not have consecutive a's can be defined by <math>(\emptyset^c aa \emptyset^c)^c</math>. Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids.
| Property | Value |
|---|
| dbpprop:abstract
|
- A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, boolean operators and concatenation but no Kleene star. For instance, the language of words over the alphabet {a,b} that do not have consecutive a's can be defined by <math>(\emptyset^c aa \emptyset^c)^c</math>. Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids. They can also be characterized logically as languages definable in FO[<], the first-order logic over the less-than relation but without the BIT predicate and as languages definable in linear temporal logic.
|
| dbpprop:hasPhotoCollection
| |
| rdf:type
| |
| rdfs:comment
|
- A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, boolean operators and concatenation but no Kleene star. For instance, the language of words over the alphabet {a,b} that do not have consecutive a's can be defined by <math>(\emptyset^c aa \emptyset^c)^c</math>. Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids.
|
| rdfs:label
| |
| owl:sameAs
| |
| skos:subject
| |
| foaf:page
| |
| is dbpprop:redirect
of | |
| is owl:sameAs
of | |
![[RDF Data]](/statics/sw-cube.png)
