Loyola College Formal Languages And Automata Question Papers

Loyola College M.Sc. Mathematics April 2012 Formal Languages And Automata Question Paper PDF Download

by

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.Sc. DEGREE EXAMINATION – MATHEMATICS

SECOND SEMESTER – APRIL 2012

MT 2960 – FORMAL LANGUAGES AND AUTOMATA

 

 

Date : 26-04-2012             Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

 

 

ANSWER ALL QUESTIONS

 

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

that end in 111.

[OR]

  1. b) Construct a DFA accepting all strings in (0 + 1)* having odd number of zeros.    (5)

 

 

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

that there exists a deterministic finite automation that accepts L.

ii)Write a note on Epsilon-Closure and give an example.                                  (10+5)

[OR]

  1. d) i)Let r be a regular expression. Then prove that there exists an NFA with

– transitions that accepts L(r).

  1. ii) An NFA has moves.

Find an  equivalent DFA.                                                                                 (8+7)

 

 

II a)   Prove that L = { / n is an integer, n  1} is not regular.

[OR]

  1. b) State and prove pumping lemma.                                                                         (5)

 

 

  1. Minimize the following automation.

 

0 1
A B C
     B D E
     C F G
  D D E
     E F G
    *F E D
   *G G F

[OR]

 

 

 

 

d)i) State and prove any three closure properties of regular languages.

  1. ii) Construct an equivalent DFA for the following NFA

 

a b
 
 
 
 

(15)

 

III a)   Construct a grammar generating all palindromes over {0, 1}.

[OR]

  1. b) Construct a grammar to generate L = { / n is an integer, n  1}        (5)

 

  1. Write GNF grammar for for the following set of production rules

,

[OR]

  1. d) Consider a grammar with production  rules

. The terminals

are Derive an equivalent grammar in CNF                         (15)

 

IV a)   Define a PDA and give an example.

[OR]

  1. b) Construct a PDA that accepts {/ n  1} by empty stack                         (5)

 

  1. c) If a PDA  A  accepts L by empty store then prove that there exists another PDA

B accepting L by final state.

[OR]

  1. d) Let M be a PDA with    as  (q0, 0,Z0) = {( q0, XZ0)}, (q0, 0,X) = {( q0, XX)}

(q0, 1,X) = {( q1, )},  (q1, 1,X) = {( q1, )},  (q1, ,X) = {( q1, )},

(q1,,Z0) = {( q1, )}. Construct a CFG generating  N(M).                      (15)

 

 

V a)  Design a  Turing Machine to add two positive integers.                      .

[OR]

  1. b) Design a Turing Machine to compute .                               (5)

 

  1. c)  Design a TM to accept the language L = { }

[OR]

  1. d) Design a TM to perform proper subtraction. (15)

 

Go To Main page

 

 

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

by

   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={anbn / n1}.
  • Show that every context – free language is a context – sensitive language.
  • If L = { L={anb / n1}then find LR
  • 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.
  1. 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

  1. Prove that CSL is closed under union.
  2. Find a grammar generating L={anbncm/ n1, m0}
  3. Write a note on Chomskian hierarchy.
  4. Prove that L= {} is not a CFL.
  5. Prove that PSL is closed under star.
  6. Give an ambiguous and an unambiguous grammar to generate L={anbn / n1}.
  7. Give a deterministic finite automation accepting the set of all strings over {0,1} with three consecutive 1’s.
  8. 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

 

  1. a) Write a note on the construction of CNF
  2. b) Write a grammar in CNF to generate L= {anbman/ n0, m1}              (5+15)

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.

  1. ii) Construct a DFA accepting all strings over {0,1} having even number of 0’s.

(10+10)

 

Go To Main Page

 

Loyola College B.Sc. Mathematics April 2007 Formal Languages And Automata Question Paper PDF Download

by

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

  1. Prove that PSL is closed under union.
  2. 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
  3. Construct a grammar G for the language L(G) = {anbam / n, m 1}
  4. Discuss about the Chomskian hierarchy
  5. Prove that L={ai / i is a prime} is not a CFL.
  6. Give an ambiguous and an unambiguous grammar to generate L={anbn / n1}.
  7. Construct a DFA to test whether a given positive integer is divisible by 3.
  8. 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

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

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

  1. State and prove uvwxy theorem.
b
a
  1. Construct a DFA for the NDFA given below

 

 

a                           b

 

 

  1. a) Construct a DFA accepting all strings over {0,1} having even number of 0’s.
  2. 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

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

by

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

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

by

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

AB 16

 

   B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – November 2008

MT 5407 – FORMAL LANGUAGES AND AUTOMATA

 

 

 

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

Time : 9:00 – 12:00

SECTION A

Answer ALL the questions:                                                                                       (102=20)

 

  1. Define a context sensitive grammar.
  2. Show that the language L ={is accepted by the grammar

G= ({S},{a,b,c}P,S) where P consists of the productions S → , S → bc.

  1. Define concatenation of two languages.
  2. Check whether the families of Phrase structure language and Context sensitive language are closed under intersection. Justify your answer.
  3. Let G = (N, T, P, S), where N = {S,A}, T = {a, b} and P consists of the rules S → aAb,

S → abSb, S → a, A → bS, A → aAAb. Check whether the grammar is ambiguous or unambiguous.

  1. Define leftmost derivation.
  2. Define Chomsky normal form.
  3. Define Self embedding property.
  4. What is the difference between deterministic finite automaton and non-deterministic finite automaton?
  5. Draw the state diagram for the non-deterministic finite state automaton M = (K, I, , , F) where K =   , I = {0,1}, F = {}  and δ is defined as follows,

 

       δ      0      1
 

 

 

SECTION B

Answer any FIVE questions:                                                                                     (5=40)

 

  1. (a) Give a context sensitive grammar to generate L = .

(b) Let L = . Show that L is generated by the regular grammar             G = (N, T, P, S) where N = {S, A}, T = {a, b} and P consists of the rules S → aS,            S → aA, A →bA, A →b.

  1. (a) Define regular grammar.

(b) Let L =   Show that a Context free grammar generating L is given by

G = (N. T, P, S) where  N = {S,A}, T = {a, b} and P consists of the following productions: S → aSb, S →aAb,    A →bA, A →b.

  1. Prove that the families of Phrase structure language, Context sensitive language, Context free language and Regular language are closed under union and product.
  2. Prove that the families of Phrase structure language, Context sensitive language, Context free language and Regular language are closed under inverse homomorphism. Prove also that the family of Context free language is not closed under intersection.
  3. Show that the grammar G =where = { S, ,V,

= { They, are, flying, planes}, = { S → () ,  → They,  (V) (,

V → are, , A →flying, V → (Aux) (P), Aux → are, → N, P → flying} and S is the start symbol, generates the language consisting of the sentence { They are flying planes}.

  1. Write a grammar in Chomsky normal form to generate L= .
  2. Let L be accepted by a non- deterministic finite automata. Then show that there exists a deterministic finite automaton that accepts L.
  3. Draw the state diagram for the following finite state automaton, M = (K, I, , , F) where K = {}, I = {a, b, c}, F = { is defined as follows,

 

        a      b      c
       Φ

 

SECTION C

Answer any TWO questions:                                                                                     (220=40)

 

  1. (a) Let L = . Prove that a context free grammar generating L is

G  =  ( {S,A}, {a, b}, P, S) where P consists of the rules S → aSb, S → aAb, A → bAa,

A → ba.

(b) Define Kleene closure and reflection of the language L.

(c) Prove that the families of Phrase structure language, Context sensitive language, Context free language and Regular language are closed under reflection.

  1. (a) Let G = (N, T, P,S) where  N = {S}, T = {a}, P = { S → SS, S → a}. Show that the grammar is ambiguous.

(b) Given a context free grammar  G = (N, T, P,S), prove that there exists an equivalent context free grammar such that for each non-terminal A S in G,

=  is infinite.

(c) Write the construction of a grammar in Greibach normal form.

  1. State and prove u-v theorem and illustrate it with example.
  2. Given a finite state automaton M, prove that there exists a right-linear grammar G such that L(G) is set accepted by M and illustrate it with an example for non-deterministic finite state automata.

 

 

Go To Main Page

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur