LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

CV 19

B.Sc.  DEGREE EXAMINATION –MATHEMATICS

FIFTH SEMESTER – APRIL 2007

MT 5404 – FORMAL LANGUAGES AND AUTOMATA

 

 

Date & Time: 04/05/2007 / 1:00 – 4:00          Dept. No.                                                     Max. : 100 Marks

 

 

PART A

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

1. Define context – free grammar and give an example.
2. Write a grammar to generate all palindromes over {a,b}
3. Show that every regular language is a context free language.
4. Define the concatenation of two languages and give an example.
5. Show that the PSL is closed under reflection.
6. Define an unambiguous grammar.
7. Show that SSS, Sa, Sb is ambiguous.
8. Construct a finite automation that accepts exactly those input strings of 0’s and 1’s that end in 11.
9. Construct a DFA to test whether a given positive integer is divisible by 2.
10. Define a non – deterministic finite automation.

PART B

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

11. Prove that PSL is closed under union.
12. Let G be a grammar with SAaS|SS|a, ASbA|SS|ba. For the string aabbaaa find
    1. a left most derivation
    2. a right most derivation
13. Construct a grammar G for the language L(G) = {aⁿba^m / n, m 1}
14. Discuss about the Chomskian hierarchy
15. Prove that L={aⁱ / i is a prime} is not a CFL.
16. Give an ambiguous and an unambiguous grammar to generate L={aⁿbⁿ / n1}.
17. Construct a DFA to test whether a given positive integer is divisible by 3.
18. Give a deterministic finite automation accepting the set of all strings over {0,1} with three consecutive 0’s.

PART C

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

19. a) Write a note on the construction of CNF
20. b) Find a grammar in CNF equivalent to a grammar whose productions are

SaAbB,  AaA|a,  BbB|b                                                           (5+15)

20. State and prove uvwxy theorem.

b

a

21. Construct a DFA for the NDFA given below

 

 

a                           b

 

 

22. a) Construct a DFA accepting all strings over {0,1} having even number of 0’s.
23. b) Let G = ( N, T, P, S), N = {S, A},   T = {a,b},   P = { SaA,  A bS, Ab}.

Find L(G) and also construct an NDFA accepting L(G)         (10+10)

 

 

Go To Main Page

Latest Govt Job & Exam Updates:

View Full List ...