CS402 Final term Subjective Papers 1

CS402 Theory of Automata Finalterm Subjective Papers

Finalterm Paper 2011 

Total questions = 52
2 marks questions

•  What is Transition?
•  Alternative form of this production        S=>aS, S=> bS, S=> A(Null).
•  What is input Tap?
•  What is live production?

3 marks questions

•  Differentiate between Distinguishable and Indistinguishable strings.
•  What is wanted and unwanted branches.
•  Table given of arbitrary summary.
•  Find Pref(Q in R).

5 marks questions:

•  What is unit of production.
•  What do u know about NFS?
•  Define two rules ………………(Row Language.).
•  (L1UL2^C) intersection (L1^CU L2) the language or accept any thing or not?

 Final Paper 2010

1. What is Row Language?
2. What does FA stands for?
3. What are living and dead productions?
4. Given a summary table, we were required to explain it.
5. What do you mean by wanted and unwanted branches?
6. Given an FA, I had to recognize the language - EVEN-EVEN
7. Given the CFG, had to write the language (EQUAL)
8. Construct corresponding CFG for the given language.
(1) All words of even length but not multiple of 3.
(2) Palindrome (both even and odd palindrome). (5 mark)
9. Who invented Turing m/c?
10. Equivalent /non-equivalent languages.
11. What are formal languages?

      

 Finalterm Paper 2009

Time 2 Hours
Total questions 41
Objective questions 31
Subjective question 10

 Question: 31                                        (Marks 1)

Can you say that string of 0’s whose length is a perfect square is not regular?

Question: 33                                        (Marks 2)

Is the following an FA or TM?

Question: 34                                        (Marks 2)

If L is the language that accept even length strings then what strings will Lc accept?

Question: 35                                        (Marks 3)

Define Myhill Nerode theorem.

Question: 36                                        (Marks 3)

If L1,L2 and L3 be any three finite languages over Sigma = {a,b}, then how will be
(L1 INTERSECTION L2) Union (L2 INTERSECTION L3) ≠ Ø

 Question: 37                                        (Marks 3)

How you differentiate between wanted and unwanted branches while deriving a string from in the context of CFG?

 Question: 38                                        (Marks 5)

What is the difference between concatenation and intersection of two FAs and union and addition of two FAs?

 Question: 39                                        (Marks 5)

Use pumping lemma II to show that following language is not regular.

L = {an2 ; n =1,2,3,4…}

 Question: 40                                        (Marks 10)

Draw Moore Machine equivalent to the following Mealy Machine.

Question: 41                                        (Marks 10)

Write CFG of the following PDA. Also write the stack alphabet and tape alphabet.