M.Sc. (Semester III) (CBCS) Examination Oct/Nov-2017
Computer Science
FINITE AUTOMATA
Day Date: Tuesday, 21-11-2017 Max. Marks: 70
Time: 02.30 PM to 05.00 PM
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 the correct alternatives. 10
The transition function of a NFA is
Q X Σ→ Q Q X Σ→ 2Q
QX Σ→ 2n QXΣ→ Qn
Regular languages are closed under
Complementation Reversal
Both and None of these
Pumping lemma is particularly used for
To prove certain language
are not regular
Some languages are regular
and context free
Two languages are
equivalent or not
None of the above
The regular expression that will accept all the strings having exactly
over will be?
aa
b
Language of PDA is
Type 0 Type 1
Type 2 Type 3
A context free grammar is in CNF if every production is of the form

A→BC or A → A A → BC or A → a
A → a or A → B None of these
A DFA for a language having all the strings that ends ab will have
number of states.
1 2
3 4
Consider the following language L {an bn cn dn n L is
CFL but not regular
CSL but not CFL
Regular
Type 0 language but not type 1
A language accepted by a Finite automata is
Regular Context free
Page 2 of 3
SLR-MG-304
Both a and b None of the mentioned
10) A Push down automata is said to be if it has at most
one transition around all configurations.
Finite Non regular
Non-deterministic Deterministic
State True or False. 04
Regular languages are closed under intersection.
The language accepted by DFA is context free.
A Turing machine uses stack as memory.
All regular languages are context free too.
Q.2 Answer the following questions:- 08
1. What are DFA and NFA? Explain with example.
2. What is ambiguous grammar? Explain with an example.
Write short note on 06
1. Context free languages.
2. Push down Automata
Q.3 Answer the following.
Construct PDA for following language.
an bn cm dm
08
Construct NFA for following regular expression
10 0
06
Q.4 Answer the following.
Construct Turing machine for following language.
an bn n
08
Construct Regular expression for following DFA using Arden's theorem
06
Q.5 Answer the following.
Construct DFA equivalent to following NFA.
08
Prove that regular languages are closed under complement and
hormomorphism.
06
Q.6 Answer the following.
What is pumping lemma? Prove that the language 1 {0m 1m+1 m is
not regular.
08
Construct PDA for following grammar.
S → aAB aS
A → Bb a
B → Sa b
06
Page 3 of 3
SLR-MG-304
Q.7 Answer the following.
Construct following grammar in CNF.
S → aaAB
A → bAB ∈
B → Baa A ∈
08
Construct DFA for the language that accepts all the strings which start
with "a" end with "b" and having "cc" as a substring over c}.