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 $L\subset 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 $R E C (M)$ .

[edit] Examples

If M is the free monoid $Σ *$ over some alphabet $Σ$ , then the family $REC\left(\Sigma^*\right)$ is just the family of regular languages $REG\left(\Sigma^*\right)$ .