One Stop GATE Forum: Sample questions of Theory of Computation.........

Message

Que. 1      The language L={(a^k)(b^k) | k>or= 1} is
A         type 3 grammer
B         type 2 grammer
C         type 1 grammer
D         type 0 grammer

Que. 2     Recursive languages are
A         a proper superset of context free languages
B         always recognizable by pushdown automata
C         also called type zero lanugages
D         all of these

Que. 3     A grammer that is both left and right recursive for a nopn-terminal is
A         ambiguous
B         unambiguous
C         information is not sufficient to decide whether it is ambiguous or 
unambiguous
D         none of the above

Que. 4     For what values of n is 10*n*log2 (n) >2*(n^2)?
A         only n>/= 32
B         only 0< font < ="20">
C         only 20
D         only n>/=0

Que. 5     Let * be defined as x*y = x' + y.Let z = x * y .Value of z*x is
A         x' + y
B         x
C         0
D         1

Que. 6     Which of the following regular expressions over {0,1} denotes the set of all strings not containing 
          100 as a substring
A         0*(1+0)*
B         0*1010*
C         0*1*01*
D         0*(10+1)*

Que. 7     Which of the following grammer rules violate the requirements of an operator 
grammer? P,Q,R are nonterminals and r,s,t are terminals.            (i) 
P -> Q R            (ii) P -> QsR            (iii) P -> e            (iv)P 
->Qtpr
A         (i) only
B         (i) and (iii) only
C         (ii) and (iii) only
D         (iii) and (iv) only

Que. 8     indicate which ofthe following statments are true      Recursive language 
are
A         A proper superset of context free languages
B         always recognizable by pushdown automata
C         recognizable by turing machine
D         also called type-0 languages

Que. 9     Which of the following is not decidable?
A         Given a  Turing machine M,a string s and an integer k,M accepts s 
within k steps
B         Equivalence of two given Turing machines
C         Language Accepted by a given finite state machine is not empty
D         language generated by a context free grammer is not empty

Que. 10     Regarding the power of recognition of languages,Which of the following 
statments is false?
A         the non-deterministic finite-state automata are equivalent to deterministic 
finite state automata.
B         non-deterministic push down automata are equivalent to deterministic 
push down automata.
C         non-deterministic Turing machines are equivalent to deterministic 
to  push down automata.
D         non-deterministic Turing machines are equivalent to deterministic 
Turing machines

Author	Message
Arpita Groupie Joined: 04Jan2007 Online Status: Offline Posts: 73	Topic: Sample questions of Theory of Computation......... Posted: 13Feb2007 at 6:05pm
	Que. 1 The language L={(a^k)(b^k) \| k>or= 1} is A type 3 grammer B type 2 grammer C type 1 grammer D type 0 grammer Que. 2 Recursive languages are A a proper superset of context free languages B always recognizable by pushdown automata C also called type zero lanugages D all of these Que. 3 A grammer that is both left and right recursive for a nopn-terminal is A ambiguous B unambiguous C information is not sufficient to decide whether it is ambiguous or unambiguous D none of the above Que. 4 For what values of n is 10nlog2 (n) >2(n^2)? A only n>/= 32 B only 0< font < ="20"> C only 20 D only n>/=0 Que. 5 Let be defined as xy = x' + y.Let z = x y .Value of zx is A x' + y B x C 0 D 1 Que. 6 Which of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring A 0(1+0)* B 01010 C 0101* D 0(10+1) Que. 7 Which of the following grammer rules violate the requirements of an operator grammer? P,Q,R are nonterminals and r,s,t are terminals. (i) P -> Q R (ii) P -> QsR (iii) P -> e (iv)P ->Qtpr A (i) only B (i) and (iii) only C (ii) and (iii) only D (iii) and (iv) only Que. 8 indicate which ofthe following statments are true Recursive language are A A proper superset of context free languages B always recognizable by pushdown automata C recognizable by turing machine D also called type-0 languages Que. 9 Which of the following is not decidable? A Given a Turing machine M,a string s and an integer k,M accepts s within k steps B Equivalence of two given Turing machines C Language Accepted by a given finite state machine is not empty D language generated by a context free grammer is not empty Que. 10 Regarding the power of recognition of languages,Which of the following statments is false? A the non-deterministic finite-state automata are equivalent to deterministic finite state automata. B non-deterministic push down automata are equivalent to deterministic push down automata. C non-deterministic Turing machines are equivalent to deterministic to push down automata. D non-deterministic Turing machines are equivalent to deterministic Turing machines
	For more papers visit: http://onestopgate.com/gate-preparation/ Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers