Ask a question about 'Recognizable language'
Start a new discussion about 'Recognizable language'
Answer questions from other users
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 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
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
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.
Given a monoid
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...
, a language
is simply a subset
. Such a language is said to be recognizable
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
is the free monoid
over some alphabet
, then the family
is just the family of regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....