Theory of Computation — Summer 2018

Show that the CFG with productions S  a | Sa | bSS | SSb | SbS is ambiguous.

Define onto function. In each case, a relation on the set {1, 2, 3} is given. Of the three properties, reflexivity, symmetry, and transitivity, determine which ones the relation has. Give reasons. a. R = {(1, 3), (3, 1), (2, 2)} b. R = {(1, 1), (2, 2), (3, 3), (1, 2)} c. R = ϕ

Write Principle of Mathematical Induction. Prove that for every n ≥ 1,1 ∑n = n / (n + 1) i=1 i(i +1)

Explain Chomsky Hierarchy.

Convert the given Moore machine into Mealy machine. Draw state transition diagram of Mealy machine. Present Next State Output State 0 1 p r q ɛ00 p r q 110 q p s q p s 1110 r q p 011 s s r 001 s s r 111

Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form. G : S  AaA | CA | BaB A  aaBa | CDA | aa | DC B  bB | bAB | bb | aS C  Ca | bC | D D  bD | ɛ ɛ represents null.

Define Context Free Grammar. Find context-free grammar for the language: L = {aibj | i < 2j}

Show that the function f(x, y) = x + y is primitive recursive.

Explain Union Rule and Concatenation Rule for Context-Free Grammar.1

Figure shows NFA-^. Draw an FA accepting the same language.

Define Constant functions, Successor functions and Projection function.

Let Gbe the grammar S  aB | bA A  a | aS | bAA B  b | bS | aBB For string aaabbabbba, find Left most derivation and Right most derivation.

Let M , Mand Mbe the FAs pictured in Figure, recognizing languages L , L and L , respectively.3 0,1 M3 = R S 0,1 S Draw FAs recognizing the following languages. a. L U L12 b. L ∩ L13

Decide whether the given language is a CFL, and prove your answer. L = { xyx | x, y ϵ {a, b}* and |x| ≥ 1}

Construct PDA for S  0AB A  1A | 1 B  0B | 1A | 0 Trace the string 01011 using PDA.

Give transition tables for deterministic PDA recognizing following language: L = {x ϵ {a, b}* | n (x) ≠ n (x)} a b Trace it for the string abbaababbb OR2

Show using pumping lemma that the given language is not a CFL. L = { anb2nan | n ≥ 0}

Prove that There are CFLs Land Lso that L ∩ Lis not a CFL, and there is a CFL Lso that L’ is not a CFL.

For the PDA, ( {q , q }, {0, 1}, {0, 1, z }, δ, q , z ϕ ), 0 1 0 0 0, where δ is δ(q , ɛ, z ) = {(q , ɛ)}001 δ(q , 0, z ) = {(q , 0z )} δ(q , 0, 0) = {(q , 00)}00 δ(q , 1, 0) = {(q , 10)}00 δ(q , 1, 1) = {(q , 11)}00 δ(q , 0, 1) = {(q , ɛ)}01 δ(q , 0, 1) = {(q , ɛ)}11 δ(q , 0, 0) = {(q , ɛ)}11 δ(q , ɛ, z ) = {(q , ɛ)}101 Obtain CFG accepted by the above PDA.

Find a regular expression corresponding to each of the following subsets of {0, 1}* 1. The language of all strings that begin or end with 00 or 11. 2. The language of all strings containing both 11 and 010 as substrings.

Define Context-Sensitive Grammar. Write a CSG for {anbncn | n ≥ 1}.

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

Use the pumping lemma to show that following language is not regular. L = {xy | x, y ϵ {0, 1}* and y is either x or xr }

Write Short note on Church-Turing Thesis.

Draw a transition diagram for a Turing machine accepting the language {SS | S ϵ {a, b}*}.