# CS 402 Final Term Current Paper 2020 || VU Past papers 20

PAST PAPER 2020                                       Total Marks 80.

40 MCQS    ( 40 MARKS )

### Short Questions:

1)      Consider the below given sequential circuit. Determine the value of new A & new B.

Old A =1 , Old B=0, Input = 1   (3 Marks)

2)      Is there any non-regular language by CFG ? Provide Example.  (3 Marks)

3)      What will discriptive form of the following regular expression (a+b)*baba(a+b)*  (3 Marks)

4)      Provide regular expression for given TG.  (3 Marks)

5)      Identify the words which are accepted by following CFG.  (3 Marks)

S –>abA

A–>baB

B–>Aa|bb

1. abbaababba

2. abbaabb

3. abbbaabb

4. abbaababb

5. abbaabaababb

Long Questions:

1)      Draw the corresponding Mealy Machine for following table.  (5 Marks)

 Old state Inputing 0 Inputing 1 State Output State Output q0=(0, 0) (1, 0) = q2 0 (1, 0) = q2 1 q1=(0, 1) (1, 0) = q2 1 (1, 0) = q2 1 q2=(1, 0) (1, 1) = q3 0 (1, 1) = q3 1 q3=(1, 1) (1, 1) = q3 1 (1, 1) = q3 1

Note q0 as initial state

2)      Write down CFG for language defined by RE. (a+b)*a . Afterwards remove null production/productions.  (5 Marks)

3)      Derive “ baabab” & “ababaab” using CFG.  (5 Marks)

S –> b S |a X |

X–> a X |b Y |

Y–> a X|

4)      Write CFG for the regular expression (a+b)*bbb(a+b)*   (5 Marks)

5)      Let S = {aa, aba, baa}. Now consider the language S* and show that the given words are the part of S*   (5 Marks)

1.       aaaabaa

2.       baaabaabaaa

3.       baaaaababaaaa

Can any word in language S* have odd number of a’s?