M.C.A (Semester-IV) (CGPA) Examination Oct/Nov-2017
Science
FINITE AUTOMATA
Day Date: Monday, 27-11-2017 Max. Marks: 70
Time: 02.30 PM to 05.00 PM
Instructions: Questions No.1 and 2 are Compulsory.
Attempt any three questions from Q.No.3 to Q.No.7
Figures to the right indicate full marks.
Q.1 Choose the correct alternative given in the bracket. 10
There are tuples in Deterministic Finite Automata.
4 5
6 None of the above
Language accepted by finite automata is language.
Type 0 Type 1
Type 2 Type 3
Regular expression for a language accepting all the strings start with
ab and end with bba over alphabet is
ab bba ab bba
ab bba All of the above
Which of the following language is regular?
String of whose length is perfect square
Strings of are whose length is prime number
Palindrome strings of even length
Strings having odd number of
Complement of will be
a
b None of the above
If L1 and L2 are regular languages the L1-L2 is
Regular Non-Regular
Context free None of the above
According to Chomsky hierarchy type 2 languages are
languages.
Regular Context free
Context Sensitive Unrestricted
Which language is accepted by push down automata?
Context free language Non-regular language
Both and None of the above
A grammar is ambiguous if there exits more than derivation
trees.
0 1
2 3
Page 2 of 2
SLR-SM-37
10 In Push down Automata the transition function × × Γ →

Q × Γ∗ Q∗ × Γ∗
Q × Γ × None of the above
State True/False 04
Turing machine has 7 tuples.
A push down automata can only be deterministic.
All context free languages are regular also.
Regular languages are not closed under homomorphism.
Q.2 Answer the following questions. 08
What is left most, right most derivation and derivation tree?
Explain NFA and DFA with examples.
Write a short note on: 06
Turing machine
Regular languages
Q3 Construct DFA equivalent to NFA.
M q1,q3) where is given by 08
a B
→ q1
q2
*q3
Construct regular expression for following DFA by using Arden's
theorem.
06
Q4 Construct Turing machine for following language L {an bn cn n 08
Explain Chomsky hierarchy. 06
Q.5
S → BBB A
A → €
B → bB A
Convert the following grammar into CNF. 08
Prove that the language L {an bn n is not regular. 06
Q.6 Explain closure properties of regular languages. 08
S → 0AS 0
A → SS 10 0S S1A
Obtain leftmost, rightmost and derivation tree for a string "000001100" for
following grammar.
06
Q.7 Construct PDA for the language L {0n 12n n . 08
S → aAb aS
A → Bb a
B → Sa b