LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

AB 25

   B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – November 2008

MT 5404 – FORMAL LANGUAGES AND AUTOMATA

 

 

 

Date : 14-11-08                     Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

PART-A

Answer ALL questions.                                                                                    (10 x2 = 20)

 

1)   If T = {0,1} then write any four elements of T ⁺.

2)   Define a regular grammar.

3)   Give an example for a context-free grammar.

4)   Prove that every regular language context-free language .

5)   Show that the family of PSL is closed under star.

6)   Define a derivation tree.

7)   Prove that G =  is ambiguous.

8)   Define a language accepted by a deterministic finite automation

9)   Define a nondeterministic finite automation.

10) Construct a DFA accepting all strings in (0 + 1)* ending with 1.

 

PART-B

Answer ANY FIVE questions.                                                             (5  x  8 = 40)

 

11) Let G be a grammar with  SAaS / SS/a  ,     A SbA / SS /ba .  For the string

aabbaaa  find   i)  a leftmost derivation

1. ii) a right most derivation

iii)  a derivation tree

12) Write a note on Chomskian hierarchy.

13) Define concatenation of two languages. Also prove that  the family of CSL is closed

under concatenation.

14) Write a CNF grammar for the language

15) Prove that  is not a context free language.

16) Let G be a grammar with productions S S + S / SS / a / b  .Find a

derivation tree for the string  ab + ab

17) Construct a finite  automation that accepts  exactly those input  strings of 0’s and1’s

that end in 101.

18) Construct a finite automation which can  test wether a given positive integer is

divisible by 2.

 

PART-C

Answer ANY TWO questions                                                                   (2 x 20 = 40 )

 

19) Let L be any context-free language. Prove that there exist constants p and q  such

that if  z  is a  word in L  with  then z can be written as   where

such that for each integer  is in L.

 

20) i) Write a note on Chomsky normal form.

1. ii) Find a grammar in CNF grammar for the language

(8 + 12)

21) Let L =consisting of an equal number of a’s and b’s}.Write a CFG

to generate L

 

22) i) Write an ambiguous and unambiguous grammar for

1. ii) Let L be a set accepted by a nondeterministic finite automation. Then prove

that there exists a deterministic finite automation that accepts L.           (8 + 12)

 

Go To Main Page

Latest Govt Job & Exam Updates:

View Full List ...