Theory Of Computation — Winter 2020

Answer the following 1.Define regular language and regular expressions. 2.Find regular expression for the following: Language of all string that do not end with 01. 3. Describe the language corresponding to following: (1+01)*(0+01)*

Answer the following: 1 Define One-to-one and Onto Functions. Also explain Compositions and Inverse of Functions. 2 Define Mathematical Induction Principle and Prove that for every n ≥ 1, n Σ i2 = n (n+1)(2n+1) / i=1

Answer the following 1.Draw FA for regular expression: (111+100)*0 2. Let M1 and M2 be the FA in fig below for the language L1 and L2, find L1 U L2 and L1 L2.

For following NFA find minimum FA accepting same language

State the pumping lemma for regular language. Prove that {0 n1 n | n >= 0} is not a regular language

Convert the Given NFA into its equivalent DFA-1

Give the context free grammar for the following languages. 1. L = { anbn |n>=0 } 2. Language for Palindroms. 3. Language for Non-Palindroms. 4. Language for Algebraic Expressions 5. L = { x belongs to {0,1}* | n (x) = n (x) } o 1 6. L = { x belongs to {0,1}* | n (x) ≠ n (x) } o 1 7. The set of odd-length strings in {a,b}* with middle symbol a.

Define NFA and NFA-Λ. Convert the following NFA to DFA

Differentiate Turing machine, PDA and FA with example.

Write Short note on Universal Turing Machine.

Draw the PDA for the following language L = {aibjck | i = j+k}

Define CFG. Prove that the following CFG is Ambiguous. SS + S | S * S | (S) | a Write the unambiguous CFG for the above grammar.

Define a Turing Machine. Design a Turing machine for deleting nth symbol from a string w from the alphabet Σ = {0,1}.

Prove that any Regular Language can be accepted by FA.

Draw Turing machine which accept palindrome language.

Prove The Theorem: “ If L1 and L2 are context – free languages, then the languages L1∪L2, L1L2 ,L1* are also CFL.”