D 91725
D 91725
THIRD SEMESTER (CUCBCSS-UG) DEGREE EXAMINATION
NOVEMBER 2020
B.C.A
BCA 3C 06-THEORY OF COMPUTATION
(2017 Admissions)
Time: Three Hours Maximum: 80 Marks
Section A
Answer all the questions. Each question carries 1 mark.
1. What is a transition system?
2. What is a mealy machine?
3. Explain relations. What are its properties?
4. Define one-to-one function with example.
5. Define grammar. 6. What is yield?
7. Define digraph.
8. What is derivation tree?
9. Find the regular expression for the set of all strings containing exactly 2a's if alphabet set
is (a, b).
10. What are the properties of a relation?
( 10 x 1 = 10 marks)
Section B
Answer all the questions. Each question carries 2 marks.
11. Define five postulates on binary operations.
12. Find the sets represented by the regular expression (a+b)* (aa+ab+bb+ba)*.
13. Explain tree and its properties.
14. Define PDA.
15. What are the properties of transition functions?
16. Find the derivation tree for the string 00110101 if grammar
G is S → OB | A, A → 0 | 0S | 1 AA, A → 1 | 1S | 0BB.
17. Define Turing Machine.
18. Explain various ways of describing a Set.
( 8 x 2 = 16 marks)
Section C
Answer any six questions. Each question carries 4 marks.
19. Explain Chomsky classification of languages.
20. Write the steps for construction of top down parser.
21. Show that the grammar G is ambiguous if S→SbS|a.
22. Find L(G), if G is S→ aS|bS|a|b.
23. Prove that the theorem: A tree with a vertices has (n - 1) edges.
24. Explain about Non Deterministic Finite State Automaton.
25. What are the identities for regular expression?
26. Explain bottom up parsing with suitable example.
27. Explain ambiguous grammars with example.
( 6 x 4 = 24 marks)
Section D
Answer any three questions. Each question carries 10 marks.
28. Construct a grammar in Greibach Normal Form equivalent to the grammar S→ AA|a,A →SS|b.
29. Prove that, If L is the set accepted by NDFA, then there exists a DFA which also accepts L
30. Explain Arden's theorem.
31. Write steps for minimization of automata with suitable example.
32. Construct a DFA if the regular expression is 10+ (0+11)0*1.
(3 x 10 = 30 marks)
നിങ്ങൾക്ക് ഉപകാരപ്പെട്ടെങ്കിൽ നിങ്ങളുടെ കൂട്ടുകാർക്ക് കൂടി ഷെയർ ചെയ്യുക
Share This
