MCA-18
June Examination 2016
MCA IIIrd Year Examination
Formal Language and Automata
Paper MCA-18
Time 3 Hours Max. Marks 80
Note: The question paper is divided into three sections B and C. Write answers as per given instructions.
Section A 8 × 2 16
(Very Short Answer Questions)
Note: Answer all questions. As per the nature of the question delimit your answer in one word, one sentence or maximum upto 30 words. Each question carries 2 marks.
What is difference between deterministic finite automata and non-deterministic finite automata?
Construct FA for the following regular expressions.
0 10 010.
What is Null String
What do you mean by Parse tree?
Write down the statement of Church Thesis.
Define grammars and name their types.
What are the productions?
(viii) Why context free grammars are called "Context Free"?
806
MCA-18 100 4 (P.T.O.)
MCA-18 100 4 (Contd.)
806
Section B 4 × 8 32
(Short Answer Questions)
Note: Answer any four questions. Each answer should not
exceed 200 words. Each question carries 8 marks.
Convert the following CFG into Chomsky Normal Form:
S
A
B
Construct PDA's that recognizes the languages:
L a n b n n 1
Check whether the given grammar is ambiguous or not
S ->iCtS
S ->iCtSeS
S
C
Explain pumping lemma for CFL. Consider the following
language L a n b n c n n≥1 using pumping lemma show
that L is not CFL.
Convert into equivalence Melay Machine
Fig. No. 1
MCA-18 100 4 (P.T.O.)
806
Give a Turing machine for the following that computes ones
complement of a binary number.
Explain Finite State Automata with the help of suitable example.
What is Greibach normal form? Write the procedure to convert
CFG into Greibach normal form.
Section C 2 × 16 32
(Long Answer Questions)
Note: Answer any two questions. Limit your answer to 500
words. Each question carries 16 marks.
10) Convert given NFA into equivalence DFA.
Fig. No. 2
11) Explain the steps involved in construction of Turing machine
in detail with the help of suitable example.
12) Explain decidability and undecidability problems, with the
help of Halt machines.
MCA-18 100 4
806
13) Construct a regular expression corresponding to the automata
given below using Arden's Theorem.
Fig. No. 3