Star-free language

Star-free language

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 (emptyset^c aa emptyset^c)^c.

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 [cite book | last=McNaughton | first=Robert | coauthors = Papert S. | year=1971 | title=Counter-free Automata | publisher=MIT Press | id=ISBN 0-262-13076-9] and as languages definable in linear temporal logic (Kamp).

ee also

*Star height problem
*Generalized star height problem

References

Further reading

*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Context-free language — In formal language theory, a context free language is a language generated by some context free grammar. The set of all context free languages is identical to the set of languages accepted by pushdown automata. Contents 1 Examples 2 Closure… …   Wikipedia

  • Deterministic context-free language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… …   Wikipedia

  • Star Wars Tales Volume 3 — Publishing company Dark Horse Comics Subject Star Wars Genre Science fiction Rel …   Wikipedia

  • Generalized star height problem — The generalized star height problem in formal language theory is the open question whether all regular languages can be expressed using regular expressions with a built in complement operator of limited star height, i. e. with a limited nesting… …   Wikipedia

  • Free Collars Kingdom — Front cover of Volume 1 フリーカラーズキングダム (Furī Karāzu Kingudamu) Genre …   Wikipedia

  • Free-to-air — (FTA) television (TV) and radio broadcasts are sent unencrypted and may be received via any suitable receiver: Free to view (FTV) is, generally, available without subscription but is digitally encoded and may be restricted geographically. Neither …   Wikipedia

  • Star Wars Tales Volume 5 — Publishing company Dark Horse Comics Subject Star Wars Genre Science fiction Rele …   Wikipedia

  • Star Wars Tales Volume 6 — Publishing company Dark Horse Comics Subject Star Wars Genre Science fiction Rele …   Wikipedia

  • Star (newspaper) — Star or The Star can refer to one of several newspapers and magazines: * The Star (Amman newspaper), an English language newspaper published in Amman, Jordan * The Star (Hong Kong) * The Star (London), a London evening newspaper founded in 1788,… …   Wikipedia

  • Star Fox (series) — Star Fox Star Fox series logo. Based on the Star Fox: Assault logo. Genres Rail shooter Action adventure game Developers …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”