Biju Patnaik University of Technology 2008-5th Sem B.Tech (B Tech), automata theory . - Question Paper
BPUT(B Tech) fifth semester , automata theory ques. paper.
Total number of printed page s - 4 _ B.Tech
BCSE 3oa
Fifth Semester Examination - 2008 AUTOMATA THEORY
Full Marks 70 .
Time-3 Hours
Answer Question No. 7 which is compulsory and sny five from the rest
IWL
The figures in the right-hand margin
as
indicate marks.
1. Answer all questions : 2 x1
(a) What'is a finite automaton ?
(b) List down five different characteristics of an automaton.
(c) What is a regular expression ?
(d) What is the Nort-Deterministic Automaton ?
P.TO.
(e) Define the meaning of terminals and non-terminais.
(f) What is the difference between grammar and language ?
(g) Write at least two differences between natural language and formal language,
(h) Distinguish between context free and context sensitive language.
(i) What do you understand by decidable ? (j) Which automata correspond to context
free language ?
2. (a) What is the formal definition of a DFA ?
How it is different from NFA ? 5 (b) Prove that for every NFA, if L is the set accepted by NFA, then there exists a DFA which also accepts L. 5
3. (a) Construct a DFA equivalent to M = ({q0f qj,
{0,1}, 5, q0, {q0}) where & is defined by
its state table as follows : 5
| ||||||||||||
|
BCSE 33QB 2 Contd* |
(b) Construct DFA for the following regular expressions,
(i) a(ab)*aa
(ii) (ab +- bb)* 5
(a) Illustrate with examples that the automaton serves a bridge between the very high* level functional description of a circuit and its logical implementation through translations, gates and flip-flops. 5
4.
IWL
5,
(b) What is the difference between MOORE and MAELY machines. 5
(a) What is the difference between a recursive language and recursively enumerable language ? 5
(b) Show that the union of two recursively enumerable languages is recursively enumerable and the union of two recursive languages is recursive, 5
6. (a) Let f(n) = 4n3 + 5n2 + 7n + 3. Prove that
f(n) - G(n3}. 5
(b) If p(n} = a/ih + an*-1 + + a,n + a0 is a polynomial of degree koverZ and a* > 0f prove that p(n) = 0{nk), 5
7. (a) Differentiate between R NP; NP-Complete
and NP-Hard problems with appropriate examples. 5
(b) Show that P is closed under (a) union, (b) concatenation, and (c) complementa-tion, 5
8. (a) Explain the Choms chy along with
the corresponds r ita. 5
(b) Show that L= {ani , n>=1} is not context-free but context-sensitive. 5
BOSE 3308
-C
4
|
Attachment: |
| Earning: Approval pending. |
