MCA-18
December 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 word. Each question carries 2 marks.
Define Universal Turing machine.
Define grammar.
What is the difference between FA and PDA?
When a language is known as recursively enumerable language?
Which data structure is used in pushdown automata?
Explain Kleene's star operation.
What is halting problem?
(viii) What is the use of Pumping Lemma?
806
MCA-18 200 3 (P.T.O.)
MCA-18 200 3 (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.
Explain how we can convert a NFA-ε to DFA.
Differentiate between the following terms and their Purpose
Final states, Trap state, non-final state
Deterministic and non-deterministic finite automata
State and explain pumping Lemma.
Write down the closure properties of regular languages.
Design DFA and NFA to recognize the following set of strings.
abb, abaa, assuming that Σ
Write a regular expression for each of the following language
over the alphabet b}.
The set of string containing ab as a substring.
The set of string having at most one pair of consecutive
and at most one pair of consecutive b's.
What is ambiguity in context free grammar?
Discuss Chomsky Hierarchy in detail with suitable diagram.
MCA-18 200 3
806
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) Construct a Turing machine over Σ to accept the
language L {0m12m
11) Find a grammar in Chomsky Normal form equivalent to
S → aAbB, A → B → bB/b.
12) Construct a PDA accepting the set of all even length
palindromes over by empty stack.
13) For the following transition table construct the minimum state
equivalent DFA. A is starting state and D is final state.
Input →
State ↓
0 1
→ A B A
B A C
C D B
D A
E D F
F G E
G F G
H G D