Theory Of Computation — Summer 2022

Draw FA for accepting:

The string in {0,1}* ending in 1 and not containing substring 00. (ii)The strings with odd no of 1’s and odd no of 0’s.

Answer the following: 1 In each case, say whether the statement is tautology, a contradiction or neither and in case of neither find a simpler statement that is logically equivalent. 1> (p → q)⋀(p → ¬q) 2> p ⋁ (p → q) 2 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. 1> R = {(1,3),(3,1),(2,2)} 2> R = ((1,1),(2,2),(3,3),(1,2)} 3> R = ø

Define δ* for! FA- NFA and NFA-Λ. Also Calculate δ* (1, ab) andδ* (1, abaab) from the following transition table.

Convert the following NFA- Λ into FA.

Convert following NFA into equivalent DFA. Draw DFA and give Transition Table for it.1

Find a minimum – state FA accepting language of the given FA.

Answer the following: 1 Find a CFG in Chomsky normal form for the following Grammar G. Ghas productions { S → SS | (S)| ∧ } 2 Give the context free grammar for the following. 1> L = { x {0,1}∗ | n (x) ≠ n (x) } o 1 2> L = { x ∈ {0,1}∗ | n (x) = n (x) } o 1

Prove “The pumping lemma for regular languages” and use it to prove that the Palindromes language is not regular.

Check whether the given grammar is in CNF S->bA|aB A->bAA|aS|a B->aBB|bS|b If it is not in CNF, Find the equivalent CNF.

Give transition table for deterministic PDA recognizing the following language. { an bn+m am | n,m ≥ 0)

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

Design and draw a deterministic PDA accepting strings with more a’s than b’s. Trace it for the string “abbabaa”.

Prove that any Regular Language can be accepted by FA.

Write Short note on Universal Turing Machine.

Construct Turing Machine to delete one letter from an alphabetic input String.

Draw a transition diagram for a Turing machine accepting the following language. { anbncn | n ≥ 0 }

Differentiate Turing machine, PDA and FA with example.