M.C.A. (Science) (Semester IV) (CBCS) Examination, 2017
FINITE AUTOMATA
Day Date: Friday, 28-04-2017 Max. Marks: 70
Time: 02.30 PM to 05.00 PM
Instruction Q.NO.1 and 2 are compulsory.
Attempt any 3 questions from Q.No3 to Q.No.7.
Figure to the right indicate full marks.
Q.1 Choose the Correct Alternatives 10
There are tuples in Grammar.
4 5 6 None of the above
NPDA stands for
Non Determinate Push Down Automata.
Non Deterministic Push Down Automata.
Non Decided Push Down Automata
None of the above.
Regular languages are closed under
Union Intersection
Both and None of the these
Number of states required to accept all the strings that ends with
10
3 2 1 Cannot be predicted
Complement of a DFA can be obtained
Making start state as final
No trial method
Making final state as non-final and non-final as final.
Making final state as start state.
A is a substitution such and non- final string for each a.
Homomorphism Closure
Interchange Inverse homomorphism
In a context free grammar the left hand side of the production rule
will be
Terminal Non-terminal/variable
Both and None of the above
In NFA the transition function x
Page 2 of 3
2Q Q None of these
According to Chomsky hierarchy type 1 languages
Regular Context free
Context Sensitive Unrestricted
10) The regular expression that will accept all the strings that will end
with ab over will be?
a
State whether true or false. 04
A DFA can have multiple final states.
Regular languages are not closed under kleene closure.
The language accepted by PAD is context free language.
A Turing machine uses stack as storage memory.
Q.2 Answer the following questions. 08
Eliminate the production and obtain equivalent grammar for the
following grammar.
What is NFA? Explain with example.
Write a short note on 06
Leftmost and rightmost derivation of a grammar.
Turing Machine.
Q.3 Convert the following grammar into CNF.
Obtain DFA equivalent to following NFA.
Q.4 What is Push Down Automata? PDA for following language.
Obtain NFA with moves for following regular expression.
Q.5 Prove that regular languages are closed under Intersection and
reversal.
Construct regular expression for following DFA. 06
What is pumping lemma? Prove that the language is
not regular.
08
Construct DFA for a language that will accept all the strings which 0
ends with 2 and having 11 as substring.
06
Q.7 What is ambiguous grammar? Remove the ambiguity form following
grammar.
What is Chomsky hierarchy? Explain in detail.