Computer Science And Engineering Theory Of Computation
1. Why are switching circuits called as finite state systems?
A switching circuit consists of a finite number of gates, each of which can be in any one of the two conditions 0 or 1.Although the voltages assume infinite set of values,the electronic circuitry is designed so that the voltages orresponding to 0 or 1 are stableand all others adjust to these value. Thus control unit of a computer is a finite statesystem.
2. 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.
3. Define: (i) Finite Automaton(FA) (ii)Transition diagram
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.
4. . What are the applications of automata theory?
_ 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.
5. What is Moore machine and Mealy machine?
A special case of FA is Moore machine in which the output depends on the state of the machine. An automaton in whch the output depends on the transition and current input is called Mealy machine.
6. 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.
7. Differentiate NFA and DFA
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).
8. What is _-closure of a state q0?
_-closure(q0 ) denotes a set of all vertices p such that there is a path from q0 to p labeled _. Example :closure(q0)={q0,q1}
9. .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 .
10. Define automaton.
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 Σ.
11. what is the principle of mathematical induction.
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.
12. List any four ways of theorem proving
(i) Deductive
(ii) If and only if
(iii) Induction
(iv) Proof by contradiction.
13. Define TOC
TOC describes the basic ideas and models underlying computing. TOC suggests various abstract models of computation, represented mathematically.
14. What are the applications of TOC?
Compiler Design
Robotics
Artificial Intelligence
Knowledge Engineering.
15. Define Transition Diagram.
Transition Diagram associated with DFA is a directed graph whose vertices corresponds to states of DFA, The edges are the transitions from one state to another.
16. What are the properties of Transition Function(δ)
(i) δ(q.ε )=q
(ii) For all strings w and input symbol a
Δ(q,aw)= δ(δ(q.a),w)
Δ(q,wa)= δ(δ(q,w).a)
(iii) The transition function δ can be extended that operates on states and strings.
17. Lists the operations on Strings.
(i) Length of a string
(ii) Empty string
(iii) Concatenation of string
(iv) Reverse of a string
(v) Power of an alphabet
(vi) Kleene closure
(vii) Substring
(viii) Palindrome
18. Lists the operations on Languages.
(i) Product
(ii) Reversal
(iii) Power
(iv) Kleene star
(v) Kleene plus
(vi) Union
(vii) Intersection
19. Define Graphs.
A graph denoted by G=(V,E) consists of a finite set of vertices (or) nodes V and a set E, a pair of vertices called edges.
20. Define Substring.
A string v appears within another string w(w=uv) is called “substring of w.” IF w=uv,then substrings u & v are said to be prefix and suffix of w respectively.
0 Response to "Computer Science And Engineering Theory Of Computation"
Post a Comment