FORMAL LANGUAGES AND
AUTOMATA THEORY
1.Introduction
In theoretical computer science, formal languages are
used to model different types of computation and to study
the properties of algorithms and automata. Regular
languages, context-free languages, and Turing machine
languages are some common examples of formal
languages used in theoretical computer science.
As an automata theory is a study of an abstract machine
as well the computation problems that can be solved using
them. So, some mathematical preliminaries and
component used to represent a machine behavior.
2. Regular Languages
Regular languages are formal languages that regular
expressions can describe and can also be recognized by
finite automata. They are used to define sets of strings,
such as sequences of characters or words, that follow
specific patterns.
They are important in computer science and theoretical
computer science because they form a foundation for
understanding the theory of computation and the design of
compilers and other software tools.
2.1. Formal Definition
Formally, a regular language can be defined as the
collection of all strings that are recognized by a finite
automata(FA).
An FA is a 5-tuple , where:
1. stands for a finite number of states
2. stands for a finite alphabet, representing the input
symbols
3. stands for the transition function which maps
to
4. stands for the initial state. It is one of the
elements of
5. stands for the set of final states. F is also a subset
of .
FAs and regular expressions specify patterns or rules that
define a language, such as sequences of characters that
must or must not appear in the strings. The words in a
regular language must follow the rules specified by the
finite automaton or regular expression to be part of the
language.
2.2. Examples of Regular Languages
Some common examples of regular languages include:
Binary strings that represent even numbers
Set of strings that contain exactly two a‘s
The set of all binary numbers that are divisible by 3
The set of all strings that contain the substring “01”
3. Characteristics of Regular Languages
Regular languages have several useful properties. Let’s
discuss some of these properties.
3.1. Closure Properties
Regular languages are closed under union,
concatenation, and Kleene star (zero or more
repetitions). This means that if two regular languages are
combined using one of these operations, the resulting
language will also be regular.
Union: Let and be regular languages,
then is a regular language
Concatenation: Let and be regular
languages, then is a regular language
Kleene Star: Let be a regular language, then is
a regular language
3.2. Regular Expressions
Regular expressions are a compact and convenient way to
define regular languages. They use a set of special
characters and operators to represent different types of
strings and sets of strings.
Let’s consider the language defined by all strings that
consist of an even number of 0’s. One way to define this
language is by using a regular expression, as follows:
In this expression, the Kleene star operation “
“ matches any number of 1’s, while the inner expression
“ ” ensures the occurrence of an even number
of 0’s and any number of 1’s. The outer Kleene star
operation ensures that the inner expression is repeated any
number of times.
3.3. Equivalence With Finite Automata
A regular language can be recognized by a finite
automata, which is a simple machine model consisting of
states, transitions, and an initial and final state.
Conversely, every regular language can be expressed
using finite automata.
In the example we considered in section 3.2, an
equivalent nondeterministic finite automaton (NFA) is
shown next using a finite automata diagram (also known
as a state diagram):
The NFA will only accept strings that end in the state ,
corresponding to an even number of 0’s in the string.
