M.C.A. (Semester IV) (CBCS) Examination Nov/Dec-2018
Science
FINITE AUTOMATA
Time: 2½ Hours Max. Marks: 70
Instructions: Question No. 1 and 2 are compulsory.
Attempt any 3 questions from Q.no.3 to Q.no.7.
Figures to the right indicate full marks.
Q.1 Choose correct alternatives. 10
Proper prefix of the string abc are
bc, abc} ε, bc}
ε, ab, abc} ε, ab}
The regular expression for Arden's algorithm is
Rij
R=R+QP
R=Q+RP None of these
If then r

None of these
Pumping lemma is used to proving given language is
Irregular Context sensitive
Restricted None of these
In GNF grammar is required in the form of
A BC a A aα
Both a and b None of these
A finite automaton with stack is known as
FA TM
DFA PDA
The language of PDA is
Context free language Regular language
Both and None of these
If rightmost and leftmost production is single non-terminal then it is
known as production.
Unit Self
Cross None of these
The machine accepts unrestricted grammar.
TM PDA
DFA None of these
10) In PDA one situation has only one transition then it is known as
TM DPDA
NPDA Stack
Fill in the blanks. 04
The transition function Q × (ΣU ε × → Q × is of
The language accepted by FA is known as
If L(r)={a,aa,aaa,aaaa,aaaaa,………..} then r
The machine has infinite tape to both ends.
Q.2 Write short notes on. 08
Instantaneous description of Turing Machine.
Construct a CFG for generating {WcWR W ε
Answer the following. 06
Construct DFA for find out given number is divisible by 3.
Construct FA. Equivalent to R.E.

Q.3 Answer the following.
Find out RE for following DFA by using Rij
07
What is pumping lemma? Using pumping lemma check {anbn+1 is
regular or not.
07
Q.4 Answer the following.
Find a grammar in GNF equivalent to grammar E
T
F
07
Design a PDA to check whether a given string over ends in abb. 07
Q.5 Answer the following.
Construct PDA that accepts the language generated by CFG.

Give the acceptance of string by PDA
07
Check whether the following grammar is ambiguous or not; if ambiguity found
remove the ambiguity and rewrite an equivalent grammar.
E
07
Q.6 Answer the following.
Construct Turing machine for string copy over Σ 07
What is halting problem? Explain with example. 07
Q.7 Answer the following.
Convert the following right linear grammar to equivalent left linear grammar
S → 0A 1B
A → 0C 1A 0
B → 1B 1A 0 1A
C → a
07
Construct CFG for PDA q0, z0,
z0)
z0) 0z0)
00)





z0)
A construct CFG, simplify CFG and describe the language accept it.