MCA-18
June Examination 2017
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.
Suppose L1 ab and L2 ba then what is concatenation of L1 and L2 (L1 o
What do you mean by 'Automata'?
What is Regular Language?
Is Regular Language is closed under concatenation operation?
806
MCA-18 200 3 (P.T.O.)
MCA-18 200 3 (Contd.)
806
Draw the Transition Diagram of the following Transition
table:
0 1
→ q0 q0 q1
q1 q1 q1
Which Language is accepted by PDA?
What is the uses of Diagonalization methods?
(viii) When does two DFAs is said to be Isomorphic?
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.
Write short note on Chomsky Hierarchy.
Explain the uses of finite automata with the help of example.
What is the use of Parse Tree? Prove that the following
Grammar is ambigous:
S → aSa bSb a b
What is Regular Expression? Find the Regular Expression
corresponding to the Language of all string over the alphabet
b that contains no more than one occurence of the string.
What do you mean by Left recursion in parsing? Remove Left
recursion from the following grammar
S → Sa Sb a
MCA-18 200 3
806
Prove that the classes of CFLs is closed under the union
operation.
Find a reduced grammar equivalent to the grammar
S → aAa
A → bBB
B → ab
C → aB
Discuss the limitations of finite Automata with suitable example.
Section C 2 × 16 32
(Long Answer Questions)
Note: Answer any two questions. You have to delimit your each
answer maximum upto 500 words. Each question carries
16 marks.
10) What do you mean by Show that L an bn cn n 1
is not context free using Pumping Lemma.
11) What do you mean by Grammar? Design CFG of the following:
L 0n 1n n 0
L 0n 12n n 0
12) Construct a deterministic PDA accepting
L W C WR W ∈ b
13) Give the definition of NDFA (Non Deterministic Finite State
Machine). Construct an NFA of the following Language
L ab a ba bb*