Theory Of Computation (2160704)

BE | Semester 7 
  Winter - 2018|27/11/2018
Total Marks 70

Q1 (a) Define one to one, onto and bijection function

  (b) Explain reflexivity, symmetry, and transitivity properties of relations

  (c) State the principle of mathematical induction and prove by mathematical induction that for all positive integers n 1+2+3+……..+n = n (n+1)/2

Q2 (a) What are the closure properties of regular languages?

  (b) Explain moore machine and mealy machine.

  (c) What are the applications of finite automata? Draw Finite Automata to accept following.

OR

  (c) Define NFA-Λ .Explain how to convert NFA-Λ into NFA and FA with suitable example

Q3 (a) State pumping lemma for regular languages.

  (b) Explain Union Rule and Concatenation Rule for Context Free Grammar

  (c) Write difference between DFA and NDFA. Convert the following NDFA to DFA.

OR

Q3 (a) Define Context-Sensitive Grammar. What is the language of following context-sensitive grammar?

  (b) Find a regular expression corresponding to each of the following subsets of {0, 1}*

  (c) What is CNF? Convert the following CFG into CNF.

Q4 (a) What is Turing Machine? Write advantages of TM over FSM

  (b) Define CFG. When a CFG is called an ‘ambiguous CFG’?

  (c) Define PDA. Describe the pushdown automata for language {0

OR

Q4 (a) Write a short note on Universal Turing Machine.

  (b) Describe recursive languages and recursively enumerable languages.

  (c) Explain push down automata with example and their application in detail

Q5 (a) Define grammar and chomsky hierarchy

  (b) What are the applications of regular expressions and finite automata?

  (c) Draw a transition diagram for a Turing machine for the language of all palindromes over {a, b}.

OR

Q5 (a) Compare FA, NFA and NFA-^

  (b) Write a short note on church-turing thesis

  (c) Explain primitive recursive function by suitable example