Computer Science And Engineering Theory Of Computation
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.