45805 - A remark on acceptance of Language

N. Lygeros

In computer science and linguistics, we have developed a vocabulary and of course mathematical techniques and theorems for dealing with a variety of types of languages. This means obviously that we made a choice between robustness and optimality. Because we need to understand a wide range of languages and not only some specific. In this context, we introduce general machines which are able to recognize language i.e. to decide if a string belongs or not to this language. In fact we can say more with the fundamental Theorem which states that a language is accepted by a finite state automaton if and only if the totality of its strings can be expressed using a regular expression i.e. a particular type of string over the alphabet formed by adjoining to A the following symbols: (,), *, v and ε. By the way, a finite state automaton is a quintuple : a finite set, called the stat set, another finite set called the alphabet, a transition function and a subset of the state set called the subset of accept states.