WBUT Exam Papers CS Formal Language And Automata Theory B Tech Sem Forth 2011

WBUT Exam Papers CS

Formal Language And Automata Theory B Tech Sem Forth 2011

Time Allotted : 3 Hours

Full Marks : 7

 

The figures in the margin indicate full marks. Candidates are required to give their answers in their own words

as far as practicable.

GROUP – A ( Multiple Choice Type Questions )

1. Choose the correct alternatives for the following : 10 x 1 = 10

i)                Moore machine output depends on

a)             input

b)             input and present state

 

c)              present state

d)             none of these.

 

ii)              FSM can recognize

a)             a grammar dependent on characteristic of FSM

b)             on CFG

c)              any unambiguous grammar

d)             only regular grammar.

 

iii)       DFA has a transition function

a) QxXtoQ                b) QxIto2<2

c) both (a) and (b)                  d) none of these.

iv)        The class of CFG is not closed under

a)           concatenation

b)          intersection

c)            union

d)           repeated concatenation.

v)          Consider the CFG

X -> zX/bX/a Y -+Ya/Yb/b

Any string of terminals, which can be generated by the CFG    .

t

a)           has at least one b

b)           ends with a

c)            has no consecutive a’s or b’s

d)           has at least 2 a’s.

vi)        A grammar that produces more than one parse tree for some sentence is said to be

a)     contiguous b) ambiguous

c)    unambiguous     cl) regular.

)01                                             o

 

vii)       The following production rules of a regular grammar generates a language L

S aS / bS / a / b

The regular expression for L is

3) a + b                                b) fa + £>)”

c) (a + fc)(a + b)*                       d) (aa + bb)ay

viii)     If Q is the number of states in the NFA, the equivalent DFA can have maximum number of states –

a)                                                                                   Q       b) Q-i

c) 2<?~ 1                                  d) 2Q.

ix)         A CFG, S -> aS/bS/a/b, is equivalent to

*

a) (a + fc,+                                  b) (a + b)(a + b{

t- ‘

c)                                                                                                                                

(a + b) (a + 6)     d) all of these.

x)           A Push down automaton is different from a finite automaton because of

a)          a read head

. ‘ • i

b)          a memory in the form of stack

c)           a set of states

d)          all of these.

[ Turn over

GROUP -B ( Short Answer Type Questions )

Answer any three of the following.      3×5= 15

£

  1. Convert the following Context-free grammar into an equivalent grammar in CNF

S -> IA/0B A -> 1AA/0S/0 B -+0BB/1S/1

  1. Is the following machine information lossless ? If yes, find the order of losslessness.

PS

NS, z

x=o

X= 1

A

A, 0

B, 0

B

C, 0

D, 0

C

D, 1

C, 1

D

B, 1

A, 1

 

  1. Let G be the grammar

S  -» aB/ba, A^a/aS/bAA, B-+b/bS/aBB For the string aaabbabbba , find

a)           leftmost derivation

b)          rightmost derivation

c)           parse tree.                                                       .

  1. Construct a Turing machine that accepts all strings over

i

{ 0, 1 } with an even number 0’s and even number of l’s.

 

  1. Test whether the following machine is definite or not

i)             by using synchronizing tree

ii)           by using repeated derivation of contracted table

iii)         if the machine is definite,

what is the order of definiteness ? Justify.

Present State

Next State

a = 0

a = 1

A

A

B

B

C

B

C

A

D

D

C

B

 

GROUP -C ( Long Answer Type Questions )

Answer any three of the following. 3 x 15 = 45


  1. a) Construct a DFA diagram from the NFA given below :

c)               What are Kleene Closure and Positive Closure ? Give example for both.                                                                          2+1

8,                            a) What do you mean by Disginghishable and Indistinguishable state ? ,                                                                            3

b)             Use Myhill Nerode Theorem to minimize the following finite automata :                                                  ?                 12

 

  1. a) Give the Regular Expression for the DFA using Arden Theorem

5

b)             What is Griebach Normal Form (GNF) for Context Free grammar ?                                                                                  1+4

Convert the following grammar into GNF

S -> ABb/a

A aaA / B

B -> bAb

c)             Using Pumping Lemma show that L = {anbn : n > 0} is not regular.                                                                           5

 

 

CS / B.TECH (CSE) / SEM-4 / CS-401 / 2011

10. a)

Construct a NFA with E or X transition

for

  r = (11 + 0)‘(00 + 1)*.

5

b)

What is PDA ?

5

c)

Construct PDA for L = {unv : w belongs to (0,1) }.

5

11. a)

What do you mean by k-equivalent states ?

3

b)

Draw the Merger graph, Merger table, Compatibility
  graph and then minimize the following :

12

 

Present

State

Next State, o/p

i/p = 0

i/p = 1

i/p =2

i/p ~ 3

A

C, 1

E, 1

B, 1

B

E, 0

C

F, 0

F, 1

D

B, 1

E

F, 0

A, 0

A l

F

C, 0

B, 0

C, 1

f

 

 

 

Leave a Comment