D 11994
D 11994
THIRD SEMESTER (CBCSS-UG) DEGREE EXAMINATION
NOVEMBER 2021
B.C.A.
BCA 3C 06-THEORY OF COMPUTATION
(2019-2020 Admissions)
Time: Two Hours Maximum : 60 Marks
Section A
Answer atleast eight questions.
Each question carries 3 marks.
All questions can be attended.
Overall ceiling 24.
1. What is Set and explain various ways of describing a set ?
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. Explain parse tree in detail.
7. Define top down parsing.
6. Define Pushdown automata.
9. If n -> 1, show that 1.1! + 2.2! + …. + n . n! (n+1)! -1.
10. What are the identities for regular expression?
11. What is a transition system?
12. Show that f: R →R {1} given by f(x)=(x+1)/(x-1) is onto.
( 8 x 3 = 24 marks)
Section B
Answer atleast five questions. Each question carries & marks.
All questions can be attended.
Overall ceiling 25.
13. Show that a connected graph G with n vertices and n-1 edges (n>_3) has at least one
leaf.
14. Explain Chomsky classification of languages.
15. Explain tree and its properties.
16. Explain ambiguous grammars. If G is the grammar S→SbS | a, check G is ambiguous or not.
17. Explain Normal Forms for Context free Grammars
18. Prove the theorems by induction: A tree with n vertices has (n-1) edges.
19. Define Turing Machine
( 5 x 5 = 25 marks)
Section C
Ansteer any one question
Eoch question carries 11 marks.
20. Prove that the theorem, if I is then there set accepted by NDFA, then there exists a DFA which also accepts I..
21. Define Chomsky normal form. Find a grammar in CNF equivalent to
S → aAD, A → aB|bA,B, B→b, D → d.
(1 x 11 = 11 marks)
നിങ്ങൾക്ക് ഉപകാരപ്പെട്ടെങ്കിൽ നിങ്ങളുടെ കൂട്ടുകാർക്ക് കൂടി ഷെയർ ചെയ്യുക
Share This
