Theory Of Computation — Winter 2018

(1) State the properties of Equivalence Relations. (2) State the strong principle of mathematical induction and show how will you give proof by induction?

(1) Prove that the statements: (p v q) → r and (p → r) v (q → r) are logically equivalent. (2) What is the regular expression of following FA?

Convert following NFA-Λ to NFA, draw the NFA. {E} ϵ A. q ∂(q, Λ) ∂ (q,0) ∂ (q,1) A {B,D} {A} Ø B Ø {C} {E} C Ø Ø {B} D Ø {E} {D} E Ø Ø Ø

Draw NFA – Λ for ((0 + 1)*10 + (00)*(11)*)* Show step by step construction.

State part-1 and part-2 of Kleens theorem and show the proof.

L1 and L2 are two languages: L1 = {x | 11 is not a substring of x} L2 = {x | x starts with 0 and ends with 0} Draw FA for both L1 and L2 and construct FA for L3 = L2 - L1\1

An NFA with states 1-5 and input alphabet {a, b} has the following transition table. q ∂(q,a) ∂(q,b) 1 {1,2} {1} 2 {3} {3} 3 {4} {4} Q.1 Draw its transition diagram 4 {5} Ø Q.2 Calculate ∂* (1,a) 5 Ø {5} Q.3 Calculate ∂* (1,aaabaab)

Convert this NFA to FA

Alanguage L {a, b}* is defined as follows: 1. a ϵ L 2. For any x ϵ L, ax ϵ L 3. For any x and y in L, all the strings bxy, xby and xyb are in L 4. No other strings are in L. Prove that every element of Lhas more a’s than b’s.

Define PDA and give PDA to accept strings of palindrome. Show trace on the string baab

Write a short note on parsing.

Define deterministic pushdown automata. Construct an example of DPDA that accepts strings with more a’s than b’s

(1) Give recursive definition for Language Pal of palindromes. (2) Give CFG equivalent to regular expression (011 + 1)* (01)*

Define Turing Machine and draw a TM to accept {a,b}*{aba}{a,b}*

Write a short note on Universal Turing Machines.

Write a note on models of computation and The Church Turing Thesis.

What is the difference between accepting a language and recognizing a language? Write short note on recursively enumerable languages.