S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
All palindromes.
All odd length palindromes.
Strings that begin and end with the same symbol
All even length palindromes.
Q.2.
Consider the following identities for regular expressions: (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true?
(a) and (b) only
(b) and (c) only
(c) and (a) only
(a), (b) and (c)
Q.3.
For S ∈ (0 +* let d(s) denote the decimal value of s (e.g. d(= 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
L is recursively enumerable, but not recursive
L is recursive, but not context-free
L is context-free, but not regular
L is regular
Q.4.
The number of tokens in the following C statement is (GATE 2000)printf("i = %d, &i = %x", i, &i);
3
26
10
21
Q.5.
The regular grammar for the language L = {anbm | n + m is even} is given by
S → S1 | S2 S1 → a S1| A1 A1 → b A1| λ S2 → aaS2| A2 A2 → b A2| λ
S → S1 | S2 S1 → a S1| aA1 S2 → aaS2| A2 A1 → b A1| λ A2 → b A2| λ
S → S1 | S2 S1 → aaa S1| aA1 S2 → aaS2| A2 A1 → b A1| λ A2 → b A2| λ
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
L2 – L1 is recursively enumerabl
L1 – L3 is recursively enumberable
L2 intersection L1 is recursively enumberable
L2 union L1 is recursively enumberable
Q.7.
The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is:
08
09
10
12
Q.8.
Consider the following two problems on undirected graphs:α: Given G(V,E), does G have an independent set of size |v|—4?β: Given G(V,E), does G have an independent set of size 5?Which one of the following is TRUE?
α is in P and β is NP-complete
α is NP complete and β is in P
Both α and β are NP-complete
Both α and β are in P
Q.9.
In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?
(L + D) *
(L.D) *
L(L + D) *
L(L.D) *
Q.10.
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
L1' is recursive and L2' is recursively enumerable
L1' is recursive and L2' is not recursively enumerable
L1' and L2' are recursively enumerable
L1' is recursively enumerable and L2' is recursive
Q.11.
Consider the languages: L1 ={a^n b^n c^m | n,m >and L2 ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE?
L1 n L2 is a context-free language
L1 u L2 is a context-free language
L1 and L2 are context-free languages
L1 n L2 is a context sensitive language
Q.12.
Consider the following decision problems:(PDoes a given finite state machine accept a given string(PDoes a given context free grammar generate an infinite number of stingsWhich of the following statements is true?
Both (P1) and (P2) are decidable
Neither (P1) nor (P2) are decidable
Only (P1) is decidable
Only (P2) is decidable
Q.13.
Consider the languages: GATE[2005]L1 = {wwR w €{*1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE?
L1 is a deterministic CFL
L2 is a deterministic CFL
L3 is a CFL, but not a deterministic CFL
L3 is a deterministic CFL
Q.14.
Consider three decision problems PP2 and PIt is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
P3 is decidable if P1 is reducible to P3
P3 is undecidable if P3 is reducible to P2
P3 is undecidable if P2 is reducible to P3
P3 is decidable if P3 is reducible to P2's complement
Q.15.
Let be the encoding of a Turing machine as a string over ∑= {1}. Let L = { |M is a Turing machine that accepts a string of length}. Then, L is
decidable and recursively enumerable
undecidable but recursively enumerable
undecidable and not recursively enumerable
decidable but not recursively enumerable
Q.16.
Consider the regular language L =(111+11111)*. The minimum number of states
3
5
8
9
Q.17.
Which of the following are decidable?I. Whether the intersection of two regular languages is infiniteII. Whether a given context-free language is regularIII. Whether two push-down automata accept the same languageIV. Whether a given grammar is context-free
I and II
I and IV
II and III
II and IV
Q.18.
Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?
L1 n L2 is a deterministic CFL
L3 n L1 is recursive
L1 U L2 is context free
L1 n L2 n L3 is recursively enumerable
Q.19.
Which of the following is true for the language {a^p} p is prine ?
It is not accepted by a turing machine
It is regular but not context free
It is context free but not regular
It is neither regular nor context free but accepted by a turing machine
Q.20.
Consider the following context free languages:L1 = {0^i 1^j 2^k | i+j = k}L2 = {0^i 1^j 2^k | i = j or j = k}L3 = {0^i 1^j | i = 2j+1}Which of the following option is true?
L1, L2 and L3 can be recognized by Deterministic Push down automata
L1, L2 can be recognized by Deterministic Push down automata
L1, L3 can be recognized by Deterministic Push down automata
None of the above
Support mcqgeeks.com by disabling your adblocker.
Please disable the adBlock and continue. Thank you.