# Education In Pakistan

## VU CS402 Theory of Automata Mid Term Examination – Spring 2006

.

CS402 Theory of Automata

Mid Term Examination – Spring 2006

Time Allowed: 90 Minutes

question:

1. This examination

neighbors.

is

closed

book,

closed

notes,

closed

a. There is no choice.

b. You will have to answer correctly all questions in this

examination to get the maximum possible marks.

3. Do not ask any questions

examination from anyone.

a. If you think that there is something wrong with any of the

questions, attempt it to the best of your understanding.

b. If you believe that some essential piece of information is

missing, make an appropriate assumption and use it to

solve the problem.

4. You are allowed to use any Software for Diagrams and Symbols

like MS Word, MathType and Visio etc.

**WARNING: Please note that Virtual University takes serious note of

unfair means. Anyone found involved in cheating will get an `F` grade in

this course.

Question No. 1

If s=abcd is a string defined over Σ = {a,bc,d} then reverse of s is dcba.

True

False

Question No. 2

Marks : 1

Marks : 10

.

Find the regular expression associated to the following FA. Show all steps.

[Hint: use FA to GTG and GTG to RE.]

Question No. 3

Σ = {aa, b}, length(aaaabaabb) = 5.

True

False

Question No. 4

Every NFA can be converted into FA.

True

False

Question No. 5

There can be more than one start states in TG.

True

False

Question No. 6

A regular language can not be infinite.

True

False

Question No. 7

Marks : 1

Marks : 1

Marks : 1

Marks : 1

Marks : 10

a) Write the recursive definition of the following language. [6]

L = Defining the language {a2n b4n }, n=1,2,3,… , of strings defined over Σ={a, b}

.

b) Write a regular expression of the language having strings that either start or end with

“00” and have no more zeroes. Where the alphabet is {0, 1}. [4]

Question No. 8

Kleene star of {1} generates {1, 11, 111, 1111, 11111 ……}.

True

False

Question No. 9

a) Define NFA-null.

b) Draw DFA for the following NFA.

Question No. 10

If a regular language is empty then we denote it like L = Ǿ (fi).

True

False

Question No. 11

Recursive method for defining language is only for regular languages.

True

False

Question No. 12

aa* = a+ ?

Marks : 1

Marks : 10

[4]

[6]

Marks : 1

Marks : 1

Marks : 1

True

False

Question No. 13

The language equal means number of a’s and b’s are equal with null string.

True

False

Marks : 1

nO�gn�h��`0001pt;line-height: normal;mso-layout-grid-align:none;text-autospace:none’>offset of the next instruction is pushed. After this it automatically clears the trap

flag and the interrupt flag to disallow further interrupts until the current routine

finishes. After this it loads the word at nx4 in IP and the word at nx4+2 in CS if

interrupt n was generated. As soon as these values are loaded in CS and IP

execution goes to the start of the interrupt handler. When the handler finishes its

work it uses the IRET instruction to return to the caller. IRET pops IP, then CS, and

then FLAGS. The original value of IF and TF is restored which re-enables further

interrupts