Q.1
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| λ
  • S → S1 | S2 S1 → aa S1| A1 S2 → aaS2| A2 A1 → bb A1| λ A2 → bb A2| λ
Q.6
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
0 h : 0 m : 1 s