M.Sc. (Semester III) (CBCS) Examination Nov/Dec-2018
Computer Science
FINITE AUTOMATA
Time 2½ Hours Max. Marks: 70
Instructions: All questions are compulsory.
Figures to the right indicate full marks.
Q.1 Multiple choice questions 14
number of states requires to accept string ending with aa.
1 2
3 Can't say
Which of the following is correct statement?
Moore machine has no accepting states
Mealy machine has accepting states
We can convert Mealy to Moore but not vice versa
All of these
is a regular expression which starts with ab then any number of
a or b and ends with bba.
ab*a*b*bba

is transition function in DFA.
Σ Q Σ Q Q Q
Σ E Σ Q Σ Q
The following production Grammar is type.

Type-1 Type-2
Type-3 Type-4
In Moore machine, output is produced over the change of
transitions state
both a and b none of these
The regular expression denote zero or more instances of an x or y is


The minimum number of productions required to produce a language
consisting of palindrome strings over Σ is
3 7
4 5
automata takes stack as auxiliary storage.
Finite automata Push down automata
Turing machine All of these
10) The relation between NFA-accepted languages and DFA accepted languages
is
8

Page 2 of 3
SLR-VG-222
11) If we select a string w such that w and w xyz. portions cannot
be an empty string?
x y
z All of these
12) In a grammer Σ For production where a ∈V and b ∈
V S
Σ Σ
13) The production of the form where A and B are non terminals is called
production.
Unit Null
CNF GNF
14) The turing machine is defined using tuples.
5 4
7 6
Q.2 Answer the following. (Any four) 08
Design RE to generate string of odd length over alphabet se
Explain Chomsky normal form.
Explain transition function in DFA.
Difference between PDA and Turing machine.
Prove that where P is RE.
Answer the following. (Any Two) 06
What is unit production? Explain how to remove unit production with
example.
Differentiate DFA and NFA.
What is need of turing machine? Explain in detail.
Q.3 Answer the following. (Any two) 08
What is Ambiguity in grammars? Explain how to remove ambiguity with
example.
What is PDA? Explain pictorial representation of PDA.
What is DFA? Explain transition Table and transition graph with example.
Answer the following. (Any one) 06
Convert following NFA to DFA where NFA is given as.

Where δ is given as
Σ a B
q0 q2
q1 q0 q1
q2 Ø
What is use of pumping lemma? Explain pumping lemma in detail.
Q.4 Answer the following. (Any two) 10
Construct grammar G for generating the string in which number of are
equal to number of 1's.
Explain undecidable problemin detail.
What is Moore machine and Mealy machine? Explain conversion of
Mealy machine to Moore machine.
Answer the following. (Any one) 04
Deign DFA which checks whether binary number is divisible by 3 or not.
Explain Closure properties or Regular Languages.
Q.5 Answer the following. (Any two) 14
Design turing machine which accepts strings consisting of even number of
zeros over alphabet set
Explain Chomsky Hierarchy in detail.
Design PDA for well-formed parenthesis.