JNTU Kakinada B-Tech 2-2 RT22055 FORMAL LANGUAGES AND AUTOMATA THEORY R13 April 2018 Question Paper

Code No: RT22055
II B. Tech II Semester Supplementary Examinations, April-2018
FORMAL LANGUAGES AND AUTOMATA THEORY (Computer Science and Engineering)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answer ALL the question in Part-A
3. Answer any THREE Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) Define FSS. (3M)
b) Define recursively enumerable language. (3M)
c) Define NFA with an example. (4M)
d) Explain about optimum DFA. (4M)
e) Define CNF. (4M)
f) What are the elements of TM?s. (4M)
PART -B
2. a) Explain about finite State Machine. (8M)
b) Is FSM is similar to FSS and FSA? Discuss. (8M)
3. a) What is the relationship between language and Grammar? Discuss. (8M)
b) Discuss about different forms of formal languages. (8M)
4. Construct the NFA for the language which accepts all and only the strings of 0?s
and 1?s that end in 01. Obtain the equivalence DFA for it.
(16M)
5. a) What is Arden?s theorem? Discuss. (8M)
b) Explain about the procedure for converting the NFA to regular expression. (8M)
6. a) Explain melay machine with an example. (4M)
b) Construct the Moore machine equivalent to the Mealy machine M defined by
table 1.
Table 1:
a=0 a=1
q1 q1 1 q2 0
q2 q4 1 q4 1
q3 q2 1 q3 1
q4 q3 0 q1 1 (12M)
7. a) How to design Turing machines? Discuss. (8M)
b) What are the components of Turing machines and give description of Turing
Machines. (8M)

1 of 1
R13
SET – 2
R13
SET – 1