BCS2143 Theory Of Computer Science

ASSIGNMENT 3

1 What is DECIDABILITY?

2 Give a proof of the following theorem:-

a) A DFA is a decidable language.

b) ANFA is a decidable language.

c) A REX is a decidable language.

d) E DFA is a decidable language.

e) Every context-free language is decidable. (refer to sipser page 172)

3. Draw a figure to describe the relationship among the four main classes of languages that we have described so far: regular, context free, decid-able, and Turing-recognizable. (refer to sipser page 173)

4. Answer all parts for the following DFA M and give reasons for your answers.


5. Let A ={| M is a DFA which doesn't accept any string containing an odd number of 1s}. Show that A is decidable.