Theory of Computation — Summer 2022

Define Equivalence Relation.

Define one-to-one function. Justify whether the function f : R  R+ defined by f(n)=n2 is bijection or not.

Draw Finite Automata to accept following over input alphabets Σ ={0, 1} 1. The language accepting strings not containing '00’ . 2. The language accepting even number of 0's and odd numbers of 1's

Define FA , NFA , NFA- Λ.

04 Find a regular expression of following subsets of {0, 1}* 1. The language of all strings that contain odd number of 1's 2. The language of all strings with next to last symbol 0.

07 Write Principle of Mathematical Induction. Prove that for every n ≥ 0, 0+1+2+3+......+n = n(n+1)/2

07 Let M1 and M2 be the FAs pictured in Figure, recognizing languages L1 and L2 respectively. Draw FAs recognizing the following languages. a. L1 U L2' b. L2 - L1

Explain ambiguous grammar with example.

Define Moore machine and Design it to generate 1’s complement of binary number..

Define Context Free Grammar. Find context-free grammar for the language: a. L = {aibjck | j=i+k} b. L = { x ∈ {0,1}∗ | n0(x) = n1(x)}.1

Explain how to Convert moore machine to mealy machine

Using subset construction method Convert NFA- Λ to NFA for following figure.

Find minimum state FA for following figure.

State the pumping lemma for Context Free Language.

Using kleene's Theorem Draw NFA-Λ for ((01)*10 + (00)*)*

Define PDA. Convert the CFG with following productions into its equivalent PDA. S → [S] | SS | ^

Write a short note on Universal Turing Machine.

Using pumping lemma prove that the language palindrome is not regular

Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form. S0A0 | 1B1 | BB, A0B | C BS1 | A C01 | Λ

Define Turing Machine.

Design a PDA to accept L = {xcxr | x ∈ (a,b)*}.

Develop a Turing Machine to accept palindromes over {a,b}*

Write a short note on Halting problem .

Design a PDA to accept L = { X / N (X) = N (X) , X ∈ {a,b}*} a b

Develop a Turing Machine to accept the language L = {WW / W ∈ {a,b}*}