Theory Of Computation — Summer 2019

Write Principle of Mathematical Induction. Using Principle of Mathematical Induction, prove that for every n≥1, n Ʃ i2 = n(n+1)(2n+1) i=1

Define reflexivity, symmetry, and transitivity properties of relations. Consider the relation R = {(1,2), (1,1), (2,1), (2,2), (3,2), (3,3)} defined over {1, 2, 3}. Is it reflexive? Symmetric? Transitive? Justify each of your answers.

Convert NFA-^ to NFA and DFA. Initial State: A, Final State : D Q δ (q, ^) δ (q, 0) δ (q, 1) A {B} {A} ϕ B {D} {C} ϕ C ϕ ϕ {B} D Φ {D} ϕ

Suppose that Land Lare the subsets12 Draw the FAs recognizing the following Languages:  L ∩ L12  L ─ L12

Define Pumping Lemma for Regular Languages. Use Pumping Lemma to show that the following languages are not regular. L = { 0n 12n | n > 0 } L = { wwR | w ϵ {0,1}* }

Define Ambiguous grammar. Write Unambiguous grammar for following grammar : E  E + E | E * E | ( E ) | id Derive string “id+id*id” using unambiguous grammar.

Given the CFG G, find a CFG G’ in Chomsky Normal form generating L(G) – { Λ} S  A | B | C A aAa | B B  bB | bb C  aCaa | D D  baD | abD | aa

Design Context Free Grammar for following Language : L = { 0i1j0k | j > i + k }

Write Regular Expressions corresponding to each of the following subsets of {0,1}*

The language of all strings in {0,1}* that containing at least two 0’s. (ii) The language of all strings containing both 101 and 010 as substrings. (iii) The language of all strings that do not end with 01.

Design PDA for the language L = { x ε {a, b}* | n (x) > n (x) }. a b

Explain Cook’s Theorem.

Design PDA for the language L = { xcxr | x ε {a, b}* }

Write Short note on Any Two :

The Primitive Recursion Function (ii) Pand NP Completeness (iii) Equivalence Relation

Design Turing Machine(TM) to accept Palindrome over {a,b}, even as well as odd.

Write Short note on Following:

Halting Problem (ii) Church Turing Thesis

Design Turing Machine to copy string.

Explain Time Complexity and Space Complexity.