Master of Computer Application II (Science)
Examination: Oct/Nov 2016 Semester IV (New CGPA)
SLR No. Day
Date Time Subject Name Paper
No. Seat No.
SLR U 30
Saturday
26/11/2016
02.30 PM
to
05.00 PM
Finite Automata
C

Instructions: Question no. 1 2 are compulsory
Attempt any three questions from Q. No. 3 to Q. No. 7
Figures to the right indicate full marks.
Total Marks: 70
Q.1 Choose correct alternatives 10
All possible subset of set is known as
sub set power set
super set none of these
Proper suffix of the string abc are


Function which mapping one to one from input to output such function is
known as function.
Machine State
Both a and b None of these
NFA is more powerful than DFA.
True False
Regular expression b)denotes the set
ba, ab, bb}
{abab} {aabb}
Pumping lemma is a
Powerful tool for providing
certain languages
non-regular
Powerful tool for providing
certain languages context
sensitive
Both a and b None of these
The context free language is not closed under
union intersection
series none of these
In GNF grammar is required in the form of
A BC a A
Both a and b None of these
A grammar that produce more than one parse tree for some sentence is
called
Context free Regular
Ambiguous None of these
10) The string anbncn can be accepted by PDA
True False
Page 1 of 2
Fill in the blanks 04
In each and every input symbol has exactly one transition from
each DFA and every state.
The empty set is denoted by
If XX, XXX, XXXX, XXXXX} then r
The grammar in which right hand side production contains at most on
non-terminal is called grammar.
Q.2 Write a short note on. 08
Pictorial representation of PDA.
Rules for conversion of RE to FA.
Answer the following 06
Design a DFA which accept number is ever or odd.
Give the applications of TM.
Q.3 Answer the following
Find regular expression for the following DFA by using Arden's theorem. 07
Construct F.A. equivalence to R.E.
(aaa
07
Q.4 Answer the followings
What is pumping lemma? Using pumping lemma check n is
regular or not.
Find a grammar in GNF equivalence to grammar E E
a
07
07
Q.5 Answer the followings
Design a PDA for language L {ai bj ck k i use final
state.
Check whether the following grammar is ambiguous or not; if ambiguity
found remove the ambiguity and rewrite an equivalent grammar.
E E E id.
07
07
Q.6 Answer the following
For the grammar S aABB aAA
A aBB a
B bBB A
C a
Obtain the corresponding PDA.
Explain closure properties of RL with example.
07
07
Q.7 Answer the following
Construct Turing machine for copy string over
How to convert PDA to CFG? Explain with example.
07
07