 # CS8501 Important 8 Mark Questions Theory Of Computation Regulation 2017 Anna University

## CS8501 Important 8 Mark Questions THEORY OF COMPUTATION

CS8501 Important 8 Mark Questions Theory Of Computation Regulation 2017 Anna University free download. Theory Of Computation Important 8 Mark Questions CS8501 pdf free download.

### Sample CS8501 Important 8 Mark Questions Theory Of Computation

(i)Explain if L is accepted by an NFA with ε-transition then show that L is accepted by an NFA without ε-transition.(6)
(ii)Construct a DFA equivalent to the NFA. M=({p,q,r},{0,1},δ,p,{q,s}) Where δ is defined in the following table.(7) CS8501 Important 8 Mark Questions Theory Of Computation

Prove for every n>=1 by mathematical induction
Σ (i)={n(n+1)/2}. (13)

Let L be a set accepted by a NFA then show that there exists a DFA that accepts L.(13)

Give the NFA that accepts all strings that end in 01.Give its transition table and the extended transition function for the input string 00101.Also construct a DFA for the above NFA using subset construction method.(13) CS8501 Important 8 Mark Questions Theory Of Computation

(i)Compose that a language L is accepted by some ε–NFA if and only if L is accepted by some DFA. (6)
(ii)Consider the following ε–NFA. Compute the ε–closure of each state and find it‟ s equivalent DFA. (7) CS8501 Important 8 Mark Questions Theory Of Computation

i)Construct the DFA to recognize odd number of 1’s and even number 0’s (7)
ii) Construct the DFA over {a,b} which produces not more than 3 a’s (6) CS8501 Important 8 Mark Questions Theory Of Computation

(i)Point out the steps in conversion of NFA to DFA and for the following convert NFA to a DFA(7)

(i)Analyze and Prove that if n is a positive integer such that n
mod 4 is 2 or 3 then n is not a perfect square.(6)
(ii)Construct a DFA that accept the string {0,1} that always ends
with 00 (7) CS8501 Important 8 Mark Questions Theory Of Computation

 Subject name THEORY OF COMPUTATION Short Name TOC Semester 5 Subject Code CS8501 Regulation 2017 regulation