Recognizable language

Recognizable language

In mathematics and computer science, a recognizable language is a formal language that is recognized by a finite state machine. Equivalently, a recognizable language is one for which the family of quotients for the syntactic relation is finite.

Definition

Given a monoid "M", a language over "M" is simply a subset Lsubset M. Such a language is said to be recognizable over "M" if there is a finite state machine over "M" that accepts "L" as an input. A finite state machine over "M" is simply one that accepts elements of "M" as input, and accepts or rejects them.

The family of recognizable languages over "M" is commonly denoted as REC(M).

Examples

If "M" is the free monoid Sigma^* over some alphabet Sigma, then the family RECleft(Sigma^* ight) is just the family of regular languages REGleft(Sigma^* ight).


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Language contact — occurs when two or more languages or varieties interact. The study of language contact is called contact linguistics. Multilingualism has likely been common throughout much of human history, and today most people in the world are multilingual.[1] …   Wikipedia

  • Language documentation — is the process by which a language is documented from a documentary linguistics perspective. It aims to “to provide a comprehensive record of the linguistic practices characteristic of a given speech community” (Himmelmann 1998:166, see also… …   Wikipedia

  • recognizable — (BrE also isable) adj. VERBS ▪ be ▪ become ▪ remain ▪ make sb/sth ▪ the mannerisms that make him instantly recognizable …   Collocations dictionary

  • Language poets — The Language poets (or L=A=N=G=U=A=G=E poets, after the magazine that bears that name) are an avant garde group or tendency in United States poetry that emerged in the late 1960s and early 1970s. In developing their poetics, members of the… …   Wikipedia

  • language — [[t]læ̱ŋgwɪʤ[/t]] ♦♦ languages 1) N COUNT A language is a system of communication which consists of a set of sounds and written symbols which are used by the people of a particular country or region for talking or writing. ...the English language …   English dictionary

  • Regular language — In theoretical computer science, a regular language is a formal language (i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties: * it can be accepted by a… …   Wikipedia

  • Finnish language — language name=Finnish nativename=suomi pronunciation=/ˈsuo.mi/ states=FIN EST Flag|Ingria Flag|Karelia NOR SWE Flag|Torne Valley region=Northern Europe speakers=about 6 million script=Latin alphabet (Finnish variant) familycolor=Uralic fam2=Finno …   Wikipedia

  • Romani language — language familycolor=Indo European name=Romani nativename=romani ćhib states=The speakers of Romani are scattered throughout the world speakers=4.8 million fam2=Indo Iranian fam3=Indo Aryan fam4=Central Zone nation=recognised as minority language …   Wikipedia

  • Franco-Provençal language — language name=Franco Provençal, Arpitan nativename=patouès, arpetan pronunciation=/patuˈe/ /patuˈɑ/ states=flag|Italy flag|France flag|Switzerland region=Valle d Aosta, Piedmont, Foggia, Franche Comté, Savoie, Bresse, Bugey, Dombes, Beaujolais,… …   Wikipedia

  • Neapolitan language — Language name=Neapolitan nativename=Napulitano states=flag|Italy region= speakers=7.5 million rank=75 85 familycolor=Indo European fam2=Italic fam3=Romance fam4=Italo Western fam5=Italo Dalmatian iso2=nap|iso3=napNeapolitan (autonym: napulitano ; …   Wikipedia

Share the article and excerpts

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