Mathematical Foundation of Computer Science

DHARM

264 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

For accepting the reverse of the strings of Language L, we can construct the MR using

above disumed points, i.e.,

l State A will be the starting state.

l Firstly choose final state B that will be the starting state. (Fig. 10.10(a))

l Next state C will be the starting state. (Fig. 10.10(b))

l Reverse the direction of transition arcs,

Thus, we get two DFA MR1 and MR2 that are shown in Fig. 10.10.

A B

0 1

1 0

C

1, 0

MR1

A B

0 1

1 0

C

1, 0

MR2
(a)(b)
Fig. 10.10
For automaton MR1 equivalent regular expression is 1. 1. 0 which is the reverse of
the first part of previous regular expression.
Similarly MR2 has equivalent regular expression (0 + 1). 0. 1. 1. 0* which is the
reverse of the second part of previous regular expression.
Hence, we see that reverse of language L are accepted by DFA MR1 or MR2.
Therefore, reverse of a regular language is also regular.

10.5DECISION PROBLEMS (DP) OF REGULAR LANGUAGES

Decision problems of regular languages are computational problems. We know the fact that

regular languages are the languages of the finite automatons. So, Finite automaton provides

computational procedure to solve the decisions problems.

A decision problems consists of a set of instances (may be infinite). On these set of

instances finite automaton take decision and answered either ‘Yes’ or ‘No’.

A regular language consists of infinite many strings and there is no finite way to represent

the complete languages. So, for the general queries about the regular languages those are

discussed below, the computational procedure exist that’s why these queries are the decision

problems of regular languages.

Following are the decision problems:

1. Emptiness problem


2. Finiteness problem


3. Membership problem


4. Equivalence problem and problem of Minimization

10.5.1(DP1)-Emptiness Problem

If L is a regular language then the question arises; Is L empty?