Recognizable language
From Wikipedia, the free 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.
[edit] Definition
Given a monoid 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 accepts elements of M as input, and accepts or rejects them.
The family of recognizable languages over M is commonly denoted as REC(M).
[edit] Examples
If M is the free monoid Σ * over some alphabet Σ, then the family is just the family of regular languages .