Abstract family of languages
An abstract family of languages is a grouping of
formal languages such that the membership of a language in a given family is proven by its sharing of specific characteristics with the languages already known to be of that family. A family must contain at least one non-empty language, and while there may be no limit to the size of alphabets in the languages of a family, there must be a finite alphabet over which each of the languages in the family are defined. [http://eom.springer.de/A/a110110.htm Springer, "abstract family of languages"] ]
formal language" is a set for which there exists a finite set of abstract symbols such that , where * is the Kleene staroperation.
A "family of languages" is an ordered pair , where
# is an infinite set of symbols;
# is a set of formal languages;
# For each in there exists a finite subset ⊂ such that ⊆ ; and
# ≠ Ø for some in .
A "trio" is a family of languages closed under
e-free homomorphism, inverse homomorphism, and intersection with regular language.
A "full trio," also called a "cone," is a trio closed under arbitrary homomorphism.
A "(full) semi-AFL" is a (full) trio closed under union.
A "(full) AFL" is a "(full) semi-AFL" closed under
concatenationand the Kleene plus.
ome families of languages
The following are some simple results from the study of abstract families of languages.
Seymour Ginsburg, "Algebraic and automata theoretic properties of formal languages", North-Holland, 1975, ISBN 0 7204 2506 9.]
Chomsky hierarchy, the regular languages, the context-free languages, and the recursively enumerable languages are all full AFLs. However, the context sensitive languages and the recursive languages are AFLs, but not full AFLs because they are not closed under arbitrary homomorphisms.
The family of regular languages are contained within any cone (full trio). Other categories of abstract families are identifiable by closure under other operations such as shuffle, reversal, or substitution. [http://eom.springer.de/a/a110430.htm Springer, "AFL operations"] ]
Seymour Ginsburgof the University of Southern Californiaand Sheila Greibachof Harvard Universityfirst presented their AFL theory paper at the IEEEEighth Annual Symposium on Switching and Automata Theory in 1967. [ [http://www.worldcat.org/oclc/2891921 IEEE conference record of 1967 Eighth Annual Symposium on Switching and Automata Theory] : papers presented at the Eighth Annual Symposium, University of Texas, October 18-20, 1967.]
* Mateescu, A; A. Salomaa. "Aspects of classical language theory" from cite book | last = Rozenburg | first = G. (ed) | coauthors = A. Salomaa (ed) | title = Handbook of Formal Languages | location = New York; Berlin | publisher = Springer-Verlag | year = 1997 | pages = pp. 175–251 | id = ISBN 3540614869
* Springer Encyclopaedia of Mathematics (online)
Wikimedia Foundation. 2010.
Look at other dictionaries:
Abstract family of acceptors — An abstract family of acceptors (AFA) is a grouping of generalized acceptors. Informally, an acceptor is a device with a finite state control, a finite number of input symbols, and an internal store with a read and write function. Each acceptor… … Wikipedia
Languages of Norway — Languages of country = Norway official = Norwegian (Bokmål and Nynorsk), Sami and Kven unofficial = regional = minority = Romani language foreign = English German French Danish sign = Norwegian Sign Language keyboard = Norwegian QWERTY keyboard… … Wikipedia
Languages of Arda — The Languages of Arda are artificial languages invented by J. R. R. Tolkien and used in his legendarium, including The Hobbit , The Lord of the Rings and The Silmarillion . They are important as an inspiration for his imaginary world and as a… … Wikipedia
Cone (formal languages) — In formal language theory, a cone is a set of formal languages that has some desirable closure properties enjoyed by some well known sets of languages, in particular by the families of regular languages, context free languages and the recursive… … Wikipedia
Uralic languages — Family of more than 30 languages spoken by some 25 million people in central and northern Eurasia. A primary division is between the Finno Ugric languages, which account for most of the languages and speakers, and the Samoyedic languages. The… … Universalium
Tibeto-Burman languages — Introduction language group within the Sino Tibetan family (Sino Tibetan languages). At the end of the 20th century, Tibeto Burman languages were spoken by approximately 57 million people; countries that had more than 1 million Tibeto… … Universalium
Adamawa languages — Infobox Language family name=Adamawa region=Cameroon, Chad, Nigeria familycolor=Niger Congo fam1=Niger Congo fam2=Atlantic Congo fam3=Volta Congo fam4=North Volta Congo fam5=Adamawa Ubangi child1=Waja Jen child2=Mbum Day child3=Leko Nimbari The… … Wikipedia
Chinese languages — or Sinitic languages Family of languages comprising one of the two branches of Sino Tibetan. They are spoken by about 95% of the inhabitants of China and by many communities of Chinese immigrants elsewhere. Linguists regard the major dialect… … Universalium
Hmong-Mien languages — or Miao Yao languages Language family of southern China, northern Vietnam, Laos, and northern Thailand, with more than nine million speakers. Hmong (Miao, Meo) has been divided into three dialect groups, Western, Central, and Northern. Beginning… … Universalium
Zapotec languages — Zapotec Diidzaj, Diza, Ditsa, Diidxazá, Tiits Së . . . Spoken in Mexico (Oaxaca, Puebla, Guerrero); USA Native speakers ca 500,000 (date missing) … Wikipedia