Code: A-20

AMIETE – CS (NEW SCHEME) – Code: AC68

Subject: FINITE AUTOMATA & FORMULA LANGUAGES

Time: 3 Hours Max. Marks: 100

NOTE: There are 9 Questions in all.

· Question 1 is compulsory and carries 20 marks. Answer to Q.1 must be written in the space provided for it in the answer book supplied and nowhere else.

· Out of the remaining EIGHT Questions, answer any FIVE Questions. Each question carries 16 marks.

· Any required data not explicitly given, may be suitably assumed and stated.

Q.1 Choose the correct or the best alternative in the following: (210)

a. Each of the following is a regular expression that denotes a subset of the language recognized by the automaton given below except

(A) 0*(11)*0* (B) 0*1 (10*1)*1

(C) (0*1(10*1)*10*+0*)* (D) 0*1(10*1)0(100)*

b. Consider the following two statements:

S1: {(O²ⁿ) | n ³ 1} is a regular language.

S2: {O^m1ⁿO^m+n | m ³ l and n ³ l} is a regular language.

Which of the following statements is correct?

(A) Only S1 is correct. (B) Only S2 is correct.

(C) Both S1 and S2 are correct. (D) None of S1 and S2 is correct.

c. Which of the following statements is true?

(A) If a language is Context Free, it can always be accepted by a Deterministic Push-Down Automaton.

(B) The union of two context free languages is context free.

(C) The intersection of two context free languages is context free.

(D) The complement of a context free language is context free.

d. Which are equivalent?

(i) (00)*( e+0) (ii) (00)* (iii) 0* (iv) 0(00)*

(A) (i) and (ii) (B) (ii) and (iii)

(C) (i) and (iii) (D) (iii) and (iv)

e. Indicate which of the following statements is true with respect to Recursive Languages:

(A) A proper superset of context free languages.

(B) Always recognizable by a Finite Automata.

(C) Recognizable by Turing Machine.

(D) Also called Regular Languages.

f. Regarding the power of recognition of Deterministic Push Down Automata, which of the following statements is false?

(A) Accepts Regular languages.

(B) Accepts all Context Free Languages.

(C) Accepts a subset of Context Free Languages.

(D) Accepts all unambiguous Context Free Grammars.

g. Which of the following grammar rules violate the requirements of being in Chomsky Normal Form? P, Q and R are non-terminals; r, s and t are terminals and e is the empty string.

(i) P ® Q R (ii) P ® Q s R (iii) P ® e (iv) P ® t

(A) (i) and (ii) only (B) (i) and (iii) only

(C) (ii) and (iii) only (D) (iii) and (iv) only

h. The simplification of grammar needs to follow the order

(i) Eliminate useless symbol (ii) Eliminate unit productions (iii) Eliminate

e-productions

(A) (i), (ii) and (iii) (B) (ii), (i) and (iii)

(C) (iii), (ii) and (i) (D) (iii), (i) and (ii)

i. If L = {aⁿb | n ³ 0}, then L² is

(A) {aⁿb aⁿb | n ³ 0}. (B) {aⁿ¹b aⁿ²b | n1 ³ 0, n2 ³ 0}.

(C) Both A and B. (D) None of the above.

j. Lexical Analyzer uses

(A) Finite Automata. (B) Push Down automata.

(C) Turing Machine. (D) all of the above.

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2 a. Define the terms – alphabet, power of an alphabet, string and language with a suitable example for each. (8)

b. Prove by induction that for every natural number n, 8ⁿ − 2ⁿ is divisible by 6. (4)

c. Briefly explain any one application of Deterministic Finite Automata. (4)

Q.3 a. Construct separate DFA to accept the following languages over the alphabet {0, 1}

(i) The set of all strings ending with 00.

(ii) Binary numbers divisible by 5. (8)

b. Define an NFA with e-transitions. Convert the following NFA to an equivalent minimized DFA: (8)

State	d
State	0	1	e
à q₀	q₁	q₁	Ф
* q₁	q₂	q₁	q₂
q₂	Ф	q₁	Ф

Q.4 a. Find regular expression for the following languages on {a, b}. (6)

(i) L = {a²ⁿb^2m | n>=0, m>=0}

(ii) L = {w: |w| mod 3 = 0}

b. Prove that every language defined by a regular expression is also accepted by a finite automaton. (6)

c. Construct an e-NFA for the language L = (a+b)*abb. (4)

Q.5 a. State pumping lemma for regular languages. Prove that the language

{0ⁿ 1^m 2ⁿ | n, m ³1} is not regular. (8)

b. Consider a grammar G whose productions are

S à aAS | a

A à SbA | SS | ba

What is the language generated by this grammar? Show that S Þ* aabbaa using Left Most Derivation and Right Most Derivation. Also construct derivation tree whose yield is aabbaa. (8)

Q.6 a. Briefly explain the working of a Push Down Automata. Define the two approaches of a language accepted by a PDA. (8)

b. Convert the grammar with the following productions to PDA accepted by empty stack.

S ® 0S1 | A

A ® 1A0 | S | e

Show the Instantaneous Descriptions of your PDA on the input 010101. (8)

Q.7 a. Eliminate useless symbols, e-productions and unit productions from the grammar with productions:

S ® a | aA | B| C, A ® aB | e, B ® aA, C ® cCD, D ® ddd (8)

b. Show that the family of CFL is not closed under intersection and complementation. (8)

Q.8 a. Assume that the current Instantaneous Description of a Turing Machine is X₁ X₂ … X_i-1q X_i…X_n. Explain the meaning of the moves: d(q, X_i) = (p, Y, L) and d(q, X_i) = (p, Y, R) along with their exceptions. (8)

b. Design a Turing Machine to accept the language {aⁿbⁿ | n ³ 1} (8)

Q.9 a. Define the following languages. Also show pictorially the relationship between them.

(i) Recursively Enumerable

(ii) Recursive

(iii) Non-Recursively Enumerable (6)

b. Briefly explain the following:

(i) Multi-Tape Turing Machine

(ii) Universal Turing Machine (10)