Theory of Computing | Semester Question Paper - Nov 2012

                                       SASTRA UNIVERSITY

                                

Year : Nov 2012                                                    Semester : Third Semester     

Subject : Theory of Computing                                Time : 3 Hrs.

                         Part-A
Answer all the questions [20*2=40 Marks]
1. Define and give an example of a transition function.
2. Sketch an FSA M with two states and work out the language generated by M.
3. Write down the production rules to generate binary palindromes.
4. True or False: Every finite language is regular. Why?
5. If L is regular and M is a subset of L, is M regular? Give reasons.
6. Define the notion epsilon-production. How is it used?
7. Distinguish between determinism and non-determinism in the class of context-free languages.
8. Sketch an FSA generating the language L={0^2,0^5,0^7,0^11,.......}.
9. What is minimization of a FSA?
10.Explain left-most derivation.
11.Define and give an example for the concept of a syntax tree.
12.Give an example of a homomorphism and inverse homomorphism.
13.What is meant by "Inherent ambiguity"?
14.True or False: Every context free language is regular. Give reasons.
15. Explain LL(k).
16.Explain the idea of a push down automaton.
17.State the Halting problem.
18.Define the notion of a computable function.
19.Give two examples of complexity classes.
20.Briefly describe the chomsky hierarchy of languages.

                             Part-B
Answer all the questions [4*15=60 Marks]
21.Using NDFAs, show that the class of regular languages are closed under unions, concatenation, Kleen closures and reversals.
(OR)
22.Construct a deterministic FSA for the following NFSA with starting state 1, accepting state 3 and transition table as given below.
State/alphabet a b
1 2 -
2 - 3
3 1 -

23.Explain the steps in SLR(1) parsing with an example.
(OR)
24.Explain the steps to convert to chomsky normal for for the following grammar
s->ASA|aB,A->B|S,B->b|epsilon.

25.Explain pumping Lemma for regular languages and prove that L={0^n|n is a square|is not regular.
(OR)
26.Explain pumping lemma for context free languages and use it to prove that L={ww|w a binary string} is not context free.

27.Define the complexity classes P, NP, NP complete and give examples.
(OR)
28.Define a Turing machine and construct a Tm that recognized the language L of balanced parentheses.

Tags : Sastra University Theory of computing question paper , Sastra University TOC question paper , Sastra University question paper , Sastra question paper , Sastra  Theory of computing question paper , Sastra TOC question paper , Sastra University Theory of computing previous year question paper , Sastra University Theory of computing old question paper ,Theory of computing question paper , Sastra University Theory of computing semester question paper , sastra previous year question paper , anna university question paper , anna university semester question paper , anna university TOC question paper