A tutorial on finite automata

On Formal Languages

To define a language we first introduce the notion of an alphabet, a finite and non-empty set of symbols, I. A string or word on I is any finite sequence of symbols belonging to I. The set of all the strings over I, including the empty string lambda is denoted by I*, also called the universal language over I. I* is an infinite and enumerable set.

Definition

A language L is any subset of I*, i. e. L is contained in I*.

We define the concatenation of two words in L, x and y, as the word obtained by appending the word y to x, and denoted by xy.

  1. the empty word lambda is the identity with respect to concatenation
  2. the concatenation is associative: that is for all words x, y and z over I, we have (xy)z = x(yz) = xyz
  3. therefore I* is a monoid with respect the concatenation - the free monoid generated by I.
We introduce some operations on languages. In order to finitely describe an infinite language various formalisms have been proposed. Among them, automata as recognising devices, and grammars as generating devices.

Different classes of formal languages have been considered. Noam Chomsky introduced a language classification. A particular class, called regular languages, is of a great importance in the study of finite automata.

Back to index