LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034 B.Sc. DEGREE EXAMINATION – MATHEMATICS

AA 12

FIFTH SEMESTER – NOV 2006

MT 5404 – FORMAL LANGUAGES AND AUTOMATA

Date & Time : 06-11-2006/9.00-12.00 Dept. No. Max. : 100 Marks

PART A

Answer all questions. Each question carries two marks. 10×2=20

Define context – sensitive language and give an example.
Write a grammar for the language L(G) = L={aⁿbⁿ / n1}.
Show that every context – free language is a context – sensitive language.
If L = { L={aⁿb / n1}then find L^R
Construct a grammar to generate the set of all strings over {a,b} beginning with a.
Define an unambiguous grammar.
Show that the grammar SSS, Sa, Sb is ambiguous.
Construct a DFA which can test whether a given positive integer is divisible by 5.
Define a non-deterministic finite automation.

Construct a finite automation that accepts exactly those input strings of 0’s and 1’s that end in 00.

PART B

Answer any five questions. Each question carries 8 marks. 5×8=40

Prove that CSL is closed under union.
Find a grammar generating L={aⁿbⁿc^m/ n1, m0}
Write a note on Chomskian hierarchy.
Prove that L= {} is not a CFL.
Prove that PSL is closed under star.
Give an ambiguous and an unambiguous grammar to generate L={aⁿbⁿ / n1}.
Give a deterministic finite automation accepting the set of all strings over {0,1} with three consecutive 1’s.
Let G = ( N, T, P, S), N = {S, A}, T = {a,b}, P = { SaA, A bS, Ab}. Find L(G). Also construct an NDFA accepting L(G).

PART C

Answer any two questions. Each question carries 20 marks. 2×20=40

20 State and prove u-v theorem

21 Let M = (K, I, , F) where K = {}, I = {a,b}, F = {}

Find the corresponding DFA.

22 i) Construct a DFA to accept all strings over {a,b} containing the substring aabb.

(10+10)

Latest Govt Job & Exam Updates:

Loyola College B.Sc. Mathematics Nov 2006 Formal Languages And Automata Question Paper PDF Download