Name of the College : Noorul Islam College of Engineering
University : Anna University
Degree : B.E
Department : Computer Science and Engineering
Subject Code/Name : CS 1303 – Theory of Computation
Document Type : Question Bank
Website : niceindia.com
Download :https://www.pdfquestion.in/uploads/ni…omputation.pdf
NICE Theory of Computation Question Bank
Unit – I
Automata :
1. What is deductive proof? :
A deductive proof consists of a sequence of statements, which starts from a hypothesis, or a given statement to a conclusion. Each step is satisfying some logical principle.
Related : Noorul Islam College of Engineering CS1014 Information Security B.E Question Bank : www.pdfquestion.in/2944.html
2.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.
3. 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.
4. Define proof by contrapositive :
It is other form of if then statement. The contra positive of the statement “if H then C” is “if not C then not H”.
5.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.
6.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).
7.Define Induction principle :
** Basis step :P(1) is true.
** Assume p(k) is true.
** P(K+1) is shown to be true.
Unit – II
Regular Expressions And Languages
1.What is a regular expression?
A regular expression is a string that describes the whole set of strings according
to certain syntax rules. These expressions are used by many text editors and utilities to
search bodies of text for certain patterns etc. Definition is: Let be an alphabet. The
regular expression over and the sets they denote are:
i. is a r.e and denotes empty set.
ii. is a r.e and denotes the set {}
iii. For each ‘a’ in , a+ is a r.e and denotes the set {a}.
2. Differentiate L* and L+
L* denotes Kleene closure and is given by L* =U Li
i=0
example : 0* ={ ,0,00,000,…………………………………}
Language includes empty words also.
L+ denotes Positive closure and is given by L+= U Li
i=1
example:0+={0,00,000,……………………………………..}
3.What is Arden’s Theorem?
Arden’s theorem helps in checking the equivalence of two regular expressions.
Let P and Q be the two regular expressions over the input alphabet . The regular
expression R is given as :
R=Q+RP
Which has a unique solution as R=QP*.
4.Write a r.e to denote a language L which accepts all the strings which begin or
end with either 00 or 11.
The r.e consists of two parts:
L1=(00+11) (any no of 0’s and 1’s)
=(00+11)(0+1)*
L2=(any no of 0’s and 1’s)(00+11)
=(0+1)*(00+11)
Hence r.e R=L1+L2
=[(00+11)(0+1)*] + [(0+1)* (00+11)]
5.Construct a r.e for the language which accepts all strings with atleast two c’s over the set ={c,b}
(b+c)* c (b+c)* c (b+c)*
Unit – III
Context Free Grammar And Languages :
1. What are the applications of Context free languages? :
Context free languages are used in :
** Defining programming languages.
** Formalizing the notion of parsing.
** Translation of programming languages.
** String processing applications.
2. What are the uses of Context free grammars? :
** Construction of compilers.
** Simplified the definition of programming languages.
** Describes the arithmetic expressions with arbitrary nesting of balanced parenthesis { (, ) }.
** Describes block structure in programming languages.
** Model neural nets.
3.Define a context free grammar
A context free grammar (CFG) is denoted as G=(V,T,P,S) where V and T are finite
set of variables and terminals respectively. V and T are disjoint. P is a finite set of
productions each is of the form A-> where A is a variable and is a string of symbols
from (V U T)*.
4.What is the language generated by CFG or G? *
The language generated by G ( L(G) ) is {w | w is in T* and S =>w .That is a G
string is in L(G) if:
(1) The string consists solely of terminals.
(2) The string can be derived from S.
5.What is : (a) CFL (b) Sentential form
L is a context free language (CFL) if it is L(G) for some CFG G.
A string of terminals and variables is called a sentential form if: *
S => ,where S is the start symbol of the grammar