Llenguatge lliure d'estrella

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.[1] Per exemple, el llenguatge de paraules de l'alfabet { a , b } {\displaystyle \{a,\,b\}} que no té as consecutives es pot definir com ( ∅ c a a ∅ c ) c {\displaystyle (\emptyset ^{c}aa\emptyset ^{c})^{c}} , on X c {\displaystyle X^{c}} denota el complement del subconjunt X {\displaystyle X} de { a , b } ∗ {\displaystyle \{a,\,b\}^{*}} .

Un exemple d'un llenguatge que no es lliure d'estrella és { ( a a ) n ∣ n ≥ 0 } {\displaystyle \{(aa)^{n}\mid n\geq 0\}} .[2]

Es va caracteritzar els llenguatges lliures d'estrella com aquells monoides sintàctics aperiòdics.[3] 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.[4][5][6]

Tots els llenguatges lliure d'estrella pertanyen a la classe de complexitat AC0.

Referències

  1. ↑ V., Lawson, Mark. Finite automata. Boca Raton: Chapman & Hall/CRC, 2004. ISBN 1584882557. 
  2. ↑ Arto., Salomaa,. Jewels of formal language theory. Rockville, Md.: Computer Science Press, 1981. ISBN 0914894692. 
  3. ↑ «On finite monoids having only trivial subgroups» (en anglès). Information and Control, 8, 2, 01-04-1965, pàg. 190–194. DOI: 10.1016/S0019-9958(65)90108-7. ISSN: 0019-9958.
  4. ↑ 1952-, Straubing, Howard,. Finite automata, formal logic, and circuit complexity. Boston: Birkhäuser, 1994. ISBN 3764337192. 
  5. ↑ Robert., McNaughton,. Counter-free automata. Cambridge, Mass.,: M.I.T. Press, [1971]. ISBN 0262130769. 
  6. ↑ «Tense logic and the theory of linear order /» (en anglès). [Consulta: 31 desembre 2018].
  • Vegeu aquesta plantilla
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
  • Tipus-0
  • —
  • Tipus-1
  • —
  • —
  • —
  • —
  • —
  • Tipus-2
  • —
  • —
  • Tipus-3
  • —
  • —
Cada categoria de llenguatges, excepte aquells marcats per *, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia.