Discussion
Ask a question about 'Recognizable language' Start a new discussion about 'Recognizable language' Answer questions from other users |
In
mathematicsMathematics 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 scienceComputer 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 languageA 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 machineA 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
monoidIn 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 languageIn theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s
.