THEORY OF COMPUTATION

1. What is a : (a) String (b) Regular language

A string x is accepted by a Finite Automaton M=(Q, Σ, δ.q0,F) if δ (q0,x)=p, for some p in F.FA accepts a string x if the sequence of transitions corresponding to the symbols of x leads from the start state to accepting state.

The language accepted by M is L(M) is the set {x | _(q0,x) is in F}. A language is regular if it is accepted by some finite automaton.

2. Define: (i) Finite Automaton(FA) (ii)Transition diagram             (Univ)

            FA consists of a finite set of states and a set of transitions from state to state that occur on input symbols chosen from an alphabet. Finite Automaton is denoted by a 5- tuple(Q,Σ, δ,q0,F),

where Q is the finite set of states ,

Σ is a finite input alphabet,

q0 in Q is the initial state,

F is the set of final states and

δ is the transition mapping function Q * Σ to Q.

Transition diagram is a directed graph in which the vertices of the graph correspond to the states of FA. If there is a transition from state q to state p on input a, then there is an arc labeled ‘ a ‘ from q to p in the transition diagram.

3. What are the applications of automata theory?  (Univ) 

_ In compiler construction.

_ In switching theory and design of digital circuits.

_ To verify the correctness of a program.

_ Design and analysis of complex software and hardware systems.

_ To design finite state machines such as Moore and mealy machines.

4. What are the components of Finite automaton model?

The components of FA model are Input tape, Read control and finite control.

(a)The input tape is divided into number of cells. Each cell can hold one i/p symbol

(b)The read head reads one symbol at a time and moves ahead.

(c)Finite control acts like a CPU. Depending on the current state and input symbol read from the input tape it changes state.

5. Differentiate NFA and DFA. (Univ)

NFA or Non Deterministic Finite Automaton is the one in which there exists many paths for a specific input from current state to next state. NFA can be used in theory of computation because they are more flexible and easier to use than DFA .

Deterministic Finite Automaton is a FA in which there is only one path for a specific input from current state to next state. There is a unique transition on each input symbol.(Write examples with diagrams).

1. Give the examples/applications designed as finite state system.

               Text editors and lexical analyzers are designed as finite state systems. A  lexical analyzer scans the symbols of a program to locate strings corresponding to identifiers, constants etc, and it has to remember limited amount of information.

2.  Define automaton. (Univ)

Automaton is a abstact computing device. It is a mathematical model of a system,with discrete inputs,outputs,states and set of tranitions from state to state that occurs on input symbols from alphabet  Σ.

3. what is the principle of  mathematical induction. (Univ)

Let P(n) be a ststement about a non negative integer n. Then the principle of  mathematical induction is that P(n) follows from

(i)                 P(1) and

(ii)               P(n-1) implies P(n) for all n>1.

Condition(i) is called the basis step and condition (ii) is called the inductive step. P(n-1) is called the induction hypothesis.

4.  List any four ways of theorem proving  (Univ)

(i)                 Deductive

(ii)               If and only if

(iii)             Induction

(iv)             Proof by contradiction.

5.  Define TOC

                  TOC describes the basic ideas and models underlying computing. TOC suggests various abstract models of computation, represented mathematically.