Recognizable language
Encyclopedia
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.
M, a language over M is simply a subset
. 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 takes elements of M as input, and accepts or does not accept them.
The family of recognizable languages over M is commonly denoted as
.
over some alphabet 
, then the family 
is just the family of regular language
s
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a recognizable language is a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
that is recognized by a finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
. Equivalently, a recognizable language is one for which the family of quotients for the syntactic relation is finite.
Definition
Given a monoidMonoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
M, a language over M is simply a subset
. 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 takes elements of M as input, and accepts or does not accept them.The family of recognizable languages over M is commonly denoted as
.Examples
If M is the free monoid over some alphabet , then the family is just the family of regular languageRegular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s
.