Automata Theory Question Paper - Dec 18 - Information Technology (Semester 4)

18views

written 5.1 years ago by

Automata Theory - Dec 18

Information Technology (Semester 4)

Total marks: 80
Total time: 3 Hours INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

Q.1. Attempt any four sub-question.

1.a. State and explain advantages and limitation of regular and context free grammar.

(5 marks) 9082

1.b. Design a Mealy machine for a binary adder.

(5 marks) 9085

1.c. Give formal defination of PDA.

(5 marks) 6467

1.d. Construct the DFA that accept set of all strings over the alphabet $\sum = \{a, b\}$ containing either the substring 'aaa' or 'bbb'.

(5 marks) 9083

1.e. Find the CNF equivalent to

$S \rightarrow aAbB$

$A \rightarrow aA|a$

$B \rightarrow bB|b$

(5 marks) 9101

2.a. What is NFA? Design a NFA for a binary number where the first and last digit is same.

(10 marks) 9084

2.b. Write a necessary function for the given automata.

enter image description here

(10 marks) 9113

3.a.i. Find a regular expression RE corresponding to the following FA.

enter image description here

(05 marks) 9087

3.a.ii. Give a regular expression for a language over the alphabet $sum = \{a, b\}$ containing two a's.

(5 marks) 9089

3.b. Construct a Mealy machine that accepts strings ending in '00' and '11'. Convert the same to moore machine.

(10 marks) 9090

4.a. Design a PDA for CFL that checks the well formedness of parenthesis i.e the language L of all balanced string of two types of paranthesis "()" and "[]".

Trace the sequence of moves made corresponding to input string (([]){}).

(10 marks) 9108

4.b. Construct a TM accepting palindromes over $\sum = \{a, b\}.$

(10 marks) 9110

5.a. Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for string 001222.

$G: S \rightarrow 0S\ |1A|2B|\epsilon$

$A \rightarrow 1A\ |2B|\epsilon$

$B \rightarrow 2B |\epsilon$

(10 marks) 6464

5.b. Design a NFA for accepting input strings that contain either the keyword 000 or the keyword 010 and convert it into an equivalent DFA.

enter image description here

(10 marks) 9091

Q.6. Write a short notes on (Any four)

6.a. Variants of Turing Machines

(5 marks) 6471

6.b. Algorithm For CFG to CNF conversion.

(5 marks) 9483

6.c. Chomsky Hierarchy.

(5 marks) 9103

6.d. Limitation of Finite Automata

(5 marks) 9092

6.e. Halting problem.

(5 marks) 9111

ADD COMMENT EDIT