Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

The decision algorithm for regular sets requires the following points to be remembered:

a. An algorithm must always terminated to be called an algorithm. Basically, an algorithm needs to have the following four characteristics:

i. An algorithm must be written using a finite number of unambiguous steps.

ii. For every possible input, only a finite number of steps are to be performed, and the algorithm is supposed to produce a result.

iii. Every time, the same and correct result is to be produced for the same input.

iv. Each step of the algorithm must have the properties as explained in (i), (ii), (iii).

b. A regular language is just a set of strings over a finite alphabet. Every regular set can be represented by a regular expression and accepted by a minimum state DFA.

We choose DFAs represented by usual notational so that we can analyses every DFA and even simulate them.

The type of questions we are concerned are such as:

i. Is the given language empty, finite or infinite?

ii. Is one regular set equivalent to another?

and so on. Now we have to establish an algorithm to answer such questions. For our purpose we use that regular sets are represented by finite automata.