Mathematical Foundation of Computer Science

DHARM

170 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Strings, by definition, are finite but the language contains infinite number of strings. So
the important constraint of these languages is to specify them in the ways that are finite. For
example, let Σ = {a}, then Σ = L = {∈, a, aa, aaa, ..........(infinite many strings)}. The infinite
strings of the language L can be equivalently represented in a finite way as, L = {a}. Consider
another illustration, where language L = {0, 1} ∪ {a}{b}. Then the language can be con-
structed, either by concatenating an arbitrary number of strings, each is either 0 or 1, or by
concatenating the string a with an arbitrary number of copies of the string b. Similarly a
language L = {0 x 0 / x ∈ {a, b}} that contains the strings x and add 0 to each end where x is an
arbitrary string formed using a and b.
· Since, we have
L^0 = {∈},
L^1 = L,
L^2 = L L = L^1 L,
L^3 = L^2 L,
...........
...........
Lk = Lk – 1 L,
...........
Then L = L^0 ∪ L^1 ∪ L^2 ∪ ............∪ Lk ∪ ........

Or, L* = ∪=

∞

k 1 L

k

Similarly we denote L+ by,

L+ = ∪

=

∞

k 1

Lk = L L* or L* L

7. 2DETERMINISTIC FINITE STATE AUTOMATA (DFSA)/

DETERMINISTIC FINITE STATE MACHINE (DFSM)/

DETERMINISTIC FINITE AUTOMATA (DFA)

Deterministic Finite State Automata refers that abstract view of machine whose transition is

one and only one after reading the sequence of inputs from each state. The abstract view of

DFSA is shown in Fig. 7.1.

a bbb... a A

T

H

DFSA

M

q 0

Fig. 7.1

M is the machine DFSA, has a tape T of finite length. Cells of the tape contain input

symbols of a string. Machine has a tape head H, the property of the head H is read only and its