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, all boolean operators – including complementation – and concatenation but no Kleene star. For instance, the language of words over the alphabet that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero. An example of a regular language which is not star-free is , i.e. the language of strings consisting of an even number of "a".
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Llenguatge lliure d'estrella (ca)
- Langage sans étoile (fr)
- Star-free language (en)
|
| rdfs:comment
| - Un llenguatge regular es diu que és un llenguatge lliure d'estrella si es pot descriure amb una expressió regular construïda amb les lletres d'un alfabet, el símbol buit, tots els operadors booleans (incloent-hi complement i concatenació) però no la clausura de Kleen. Per exemple, el llenguatge de paraules de l'alfabet que no té as consecutives es pot definir com , on denota el complement del subconjunt de . Un exemple d'un llenguatge que no es lliure d'estrella és . Tots els llenguatges lliure d'estrella pertanyen a la classe de complexitat AC0. (ca)
- 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, all boolean operators – including complementation – and concatenation but no Kleene star. For instance, the language of words over the alphabet that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero. An example of a regular language which is not star-free is , i.e. the language of strings consisting of an even number of "a". (en)
- En informatique théorique, et notamment en théorie des langages formels, un langage rationnel est sans étoile (star-free language en anglais) s'il peut être obtenu à partir des lettres d'un alphabet et de l'ensemble vide par un ensemble fini d'opérations ensemblistes d'union, intersection, de complémentaire et de concaténations, mais sans utiliser l'opération étoile. (fr)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Un llenguatge regular es diu que és un llenguatge lliure d'estrella si es pot descriure amb una expressió regular construïda amb les lletres d'un alfabet, el símbol buit, tots els operadors booleans (incloent-hi complement i concatenació) però no la clausura de Kleen. Per exemple, el llenguatge de paraules de l'alfabet que no té as consecutives es pot definir com , on denota el complement del subconjunt de . Un exemple d'un llenguatge que no es lliure d'estrella és . Es va caracteritzar els llenguatges lliures d'estrella com aquells monoides sintàctics aperiòdics. També es poden caracteritzar lògicament com llenguatges que es poden definir per FO[<], la lògica de primer ordre sobre els nombres naturals amb la relació "més petit que", també es poden caracteritzar com llenguatges sense comptadors i com a llenguatges definits per una lògica temporal lineal. Tots els llenguatges lliure d'estrella pertanyen a la classe de complexitat AC0. (ca)
- En informatique théorique, et notamment en théorie des langages formels, un langage rationnel est sans étoile (star-free language en anglais) s'il peut être obtenu à partir des lettres d'un alphabet et de l'ensemble vide par un ensemble fini d'opérations ensemblistes d'union, intersection, de complémentaire et de concaténations, mais sans utiliser l'opération étoile. Par exemple, l'ensemble de tous les mots est le complémentaire de l'ensemble vide : c'est donc un langage sans étoile. Le langage des mots sur l'alphabet qui ne contiennent pas deux lettres consécutives est aussi un langage sans étoile. En effet, c'est l'ensemble défini par , où dénote le complément d'une partie de . (fr)
- 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, all boolean operators – including complementation – and concatenation but no Kleene star. For instance, the language of words over the alphabet that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero. An example of a regular language which is not star-free is , i.e. the language of strings consisting of an even number of "a". 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 natural numbers with the less-than relation, as the counter-free languages and as languages definable in linear temporal logic. All star-free languages are in uniform AC0. (en)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)