Categories

# CS8501 Important Questions Theory Of Computation Regulation 2017 Anna University

## CS8501 Important Questions THEORY OF COMPUTATION

### Sample CS8501 Important Questions Theory Of Computation

Differentiate between DFA and NFA.

Define DFA

Define inductive proof.

Identify NFA- ε to represent a*b | c

Consider the String X=110 and y=0110 find
i) XY ii) X2 iii) YX iv) Y2 CS8501 Important Questions Theory Of Computation

Describe the following language over the input set A={a,b}
L={ anbn | n>=1}

Describe what is non-deterministic finite automata and the applications of automata theory.

Illustrate the induction principle.?

What is proof by contradiction ?

Describe an identifier with a transition diagram (automata).

Define ε-NFA CS8501 Important Questions Theory Of Computation

Summarize minimization of DFA

Give the non-deterministic automata to accept strings containing the substring 0101

Illustrate if L be a set accepted by an NFA then there exists a DFA that accepts L.

Define the term epsilon transition. CS8501 Important Questions Theory Of Computation

Summarize the extended transition function for a ε-NFA

Create a FA which accepts the only input 101 over the input set
Z={ 0,1}

Describe a Finite automata and give its types.

Illustrate deductive proof.

Create a FA which checks whether the given binary number is even.

List the operators of Regular Expressions

Differentiate between regular expression and regular language

Tabulate the regular expression for the following
L1=set of strings 0 and 1 ending in 00
L2=set of all strings 0 and 1 beginning with 0 and ending with 1

What are the closure properties of regular languages? CS8501 Important Questions Theory Of Computation

Explaina finite automaton for the regular expression 0*1*.

Illustrate a regular expression for the set of all the strings

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