SRM University 2007 B.Tech Computer Science and Engineering BANK : THEORY OF COMPUTATION - Question Paper

CS210 THEORY OF calculation

ques. BANK

PART -A
UNIT- I

1) Is it actual that the language accepted by any NDFA is various from the regular language? Justify your ans.
2) define the subsequent sets by regular expression:
(a) L1=the set of all strings of 0’s and 1’s ending in 00.
(b)L2=the set of all strings of 0’s and 1’s beginning with ‘0’
and ending with ‘1’.
3)Describe Transition system.
4)Define Deterministic automata with example.
5)Define Non-Deterministic automata with example.
6)Define NDFA with e-transition .Give example.
7)Define e-closure with example.
8)What is the difference ranging from DFA and NDFA.
9)Define acceptance of a string and language.
10)Give the regular set or language for the regular expression:
(a)1(01)*(10)*1
(b)(1+10)*001.
11)Define regular expression with example.

12)Construct DFA for the set of strings{ } ending with ‘00’.
13)Obtain the DFA equivalent to the subsequent NDFA.
F={q2},initial state={q0}
States\inputs 0 1
q0 {q0,q1} {q0}
q1 - {q2}
q2 - -

14)Obtain an NDFA without e-transition to the subsequent NDFA with E-transition:
F={q2},initial state={q0}
States\inputs 0 1 2 e
q0 {q0} - - {q1}
q1 - {q1} - {q2}
q2 - - {q2} -
15)Define Moore Machine with example.
16)Define Mealy machine with example.
17)Prove that for every Moore machine M1 there is a Mealy
machine M2.
18)State the pumping lemma for regular sets or regular language.
19)What is the use of the pumping lemma for regular sets?
20)State the application of the pumping lemma for regular sets.


UNIT-II

1)Define a grammar with example.
2)Define CFG with example.
3)State the various kinds of grammar.
4)Find L(G) where G=({S},{0,1},{S->0S1,S->E},S)
5)Define derivation tree for a CFG.
6)Let G=({S,C},{a,b},P,S) where P consists of S->aCa,
C->aCa/b.Find L(G).
7)Consider G whose productions are S->aAS/a,
A->SbA/SS/ba.Show that S=>aabbaa and construct a derivation
tree whose yield is aabbaa.
8)Define Ambiquous grammar with example.
9)Define LMD and RMD.Give example.
10)Define sentinential form with example.
11)Define useless and useful symbols.Give example.
12)When a variable is stated to be nullable?
13)Define Unit production with example and Useless production.
14)Define E-production.
15)What are the types of Normal forms.
16)Define CNF with example.
17)Define GNF with example.
18)State the difference ranging from CNF and GNF.
19)Define inherently ambiquous CFL.
20)Define A-derivable.
21)When CFG is stated to be linear grammar?
22)Define an operator grammar.

UNIT-III

1)Define Pushdown Automata.
2)Give an example of a PDA.
3)Define the acceptance of a PDA by empty stack.Is it actual that a language accepted by a PDA by empty stack or by that of final states are various languages?

Earning:   Approval pending.