First the year in which the question appears would be mentioned followed by the question and its answer.
DECEMBER 2004
1. The context-free languages are closed for :
(i) Intersection (ii) Union
(iii) Complementation (iv) Kleene Star
then
(A) (i) and (iv) (B) (i) and (iii)
(C ) (ii) and (iv) (D) (ii) and (iii)
Ans:-C
Explanation:- Context-free languages are closed under union,intersection and star-closure. Context-free languages are not closed under intersection and complementation.
June - 2005
2. Which of the following is not true ?
(A) Power of deterministic automata is equivalent to power of non-deterministic
automata.
(B) Power of deterministic pushdown automata is equivalent to power of
non-deterministic pushdown automata.
(C) Power of deterministic turing machine is equivalent to power of non-deterministic
turing machine.
(D) All the above
Ans:-B
Explanation:-
Deterministic and nondeterministic finite automata have equivalent computational capabilities.
Deterministic and nondeterministic Turing machines have the same computational capabilities.
However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata. So, the answer is B.
3. Identify the language which is not context - free.
(A) L={wwR|w is a member of {0,1}*}
(B) L={anbn|n>=0}
(C )L={ww|w is a member of {0,1}*}
(D) L={anbmcmdn|n,m>=0}
Ans:-B
December 2005
4. Which sentence can be generated by S → d/bA, A → d/ccA :
(A) bccddd
(B) aabccd
(C) ababccd
(D) abbbd
Ans:-A
Explanation:-
The most closest answer seems to be A only. The terminals in the grammar are d,b and c. There is no terminal 'a' at all. So the options B,C and D are ruled out. option A can also be derived at something like this.
S->bA
->bccA
->bccccA
->bccccd
So the sentence generated should be bccccd. If there are any other explanations for the same please post them.
5. Regular expression a+b denotes the set :
(A) {a}
(B) {Epsilon, a, b}
(C) {a, b}
(D) None of these
Ans:-C
June 2006
6. Which of the following strings is in the language defined by grammarS → OA, A → 1A/0A/1
(A) 01100
(B) 00101
(C ) 10011
(D) 11111
Ans:-B
Explanation:-
Non terminals in the above grammar are S, and A. Terminals are 0 and 1. The start symbol of the grammar is S.
S->0A. So rule out strings beginning with 1. so that leaves us with two options A and B.
S->0A
->00A
->001A
->0010A
->00101
So the option B is correct. If you try to derive the string for option A you would not be able to get it. So, the correct answer is option A.
7. The logic of pumping lemma is a good example of :
(A) pigeon hole principle
(B) recursion
(C) divide and conquer technique
(D) iteration
Ans:-A
December - 2006
8. Which of the regular expressions corresponds to this grammar ? S → AB/AS, A → a/aA, B → b
(A) aa*b+
(B) aa*b
(C ) (ab)*
(D) a(ab)*
Ans:-B
JUNE 2007
9. The regular expression given below describes :
r=(1+01)*(0+λ)
(A) Set of all string not containing '11'
(B) Set of all string not containing '00'
(C) Set of all string containing '01'
(D) Set of all string ending in '0'
Ans:-B
Explanation:-
The meaning of (1+01)* means that the set of strings of 1 and 01 of any length including the NULL string. (0+λ) means either 0 or λ. So the full regular expression stands for the set of strings of 1's and 01's of any length ending with 0 or λ. So we cannot say the string will only end in '0'. It could end in λ also. The string can begin with 1 or 01 and multiple times it can get repeated.But the string '11' cannot be together. So the option could be B.
hlo, for question no 3 ie, which is not a context free language. i think the answer is option C
ReplyDeleteL={ww|w is a member of {0,1}*
question no 3,correct answer is C
ReplyDeleteQuestion Number is wrong answer
ReplyDeletecorrect answer option c
Madame, do you coach NET aspirants in bangalore or are you aware about any coaching centres in Bangalore ?
ReplyDeleteGood questions of Automata for practice before exam and this will also help the students in internals. If anyone have problems in these questions or in other they can visit Computer Science Homework Help that is the best Assignment helper for CS students.
ReplyDeletegood explanation
ReplyDeletehello do u have more videos. if so where can i get them. pls provide links
ReplyDeleteWill upload more. keep visiting and thanks a lot.
Delete