QUESTION BANK
Q1. Choose the correct statement. [GATE 2003]
The set of all strings over an alphabet S ={0,1} with the concatenation operator for strings
a) does not form a group
b) forms a noncommutative group
c) does not have a right identity
d) forms a group if the empty string is removed from S *
CHOOSE YOUR ANSWERQ2. Consider the set of all strings S * over an alphabet S ={a,b} with the concatenation operator for strings, and choose the false statement
a) the set does forms semigroup
b) the set does not form a group
c) the set has a left and right identity
d) the set forms a monoid
CHOOSE YOUR ANSWERQ3. Consider the set of all strings S * over the alphabet S ={a,b,c,d,e} with the concatenation operator for strings. Choose the false statement
a. the set has a right identity and forms a semigroup
b. the set has a left identity and forms a monoid
c. the set does not form a commutative group but has an identity
d. the set does not form a semigroup with identity
CHOOSE YOUR ANSWERQ4. Nobody knows yet if P = NP. Consider the language L defined as follows:
L=()+1)* if P = NP
And
L=j otherwise
Which of the following statements is true?
a) L is recursive
b) L is recursively enumerable but not recursive
c) L is not recursively enumerable
d) Whether L is recursive or not will be known after we find out if P = NP
CHOOSE YOUR ANSWER[GATE 2003]
Q5. Consider the language defined as follows
L= {a^n b^nn>=1} if P=NP
And
L={www in (a+b)+} otherwise
Which of the following statements is true?
a) L is recursive but not context sensitive
b) L is context sensitive but not context free
c) L is context sensitive
d) What L is will be known after we resolve the P=NP question
CHOOSE YOUR ANSWERQ6. Consider the language defined as follows
L=(0+1)* if the CSLs are closed under complement
And
L=(0*1)*0* if P=NP
And
L=(10*)1* if P is not the same as NP
Which of the following statements is true?
a) L is always a regular set
b) L does not exist
c) L is recursive but not a regular set
d) What L is will be known after the two open problems P = NP and the closure of CSLs under complement are resolved
CHOOSE YOUR ANSWERQ7. Consider the language defined as follows
L=(0+1)* if man goes to Mars by 2020AD
And
L=0* if man never goes to the Mars
Which of the following is true?
a. L is context free language but not recursive
b. L is recursive
c. Whether L is recursive or not will be known in 2020AD
d. L is a r.e. set that is not regular
CHOOSE YOUR ANSWERQ8. Given an arbitrary context free grammar G, we define L as below.
L=(0+1)* if G is ambiguous
And
L=j if G is not ambiguous
Choose the true statement
a. L is a contextfree language
b. L is recursive but not r.e.
c. What L is depends on whether we can determine if G is ambiguous or not
d. What L is is undecidable
CHOOSE YOUR ANSWERQ9. Given an arbitrary turing machine M and a string w we define L as below.
L=(0*1)*0* if M halts on w
And
L=(0*1*)* if M does not halt on w
Choose the correct statement?
a. The type of L is undecidable because of the halting problem
b. L is a contextsensitive language
c. L is recursively enumerable and not contextfree
d. L is context sensitive and not regular
CHOOSE YOUR ANSWERQ10. Consider the language L defined below
L=(0+1)* if P=NP
And
L=(a^nb^nn>=1} otherwise
Choose the false statement
a. Whether L is a regular set that is not contextfree will be known after we resolve the P=NP question.
b. Whether L is contextfree but not regular will be known after we resolve the P=NP question
c. L is contextsensitive
d. L is not recursive
CHOOSE YOUR ANSWERQ11. It is undecidable if two cfls L1 and L2 are equivalent. Consider two cfls L1 and L2 and a language defined as follows
L={a^nb^nc^nn>=234} if L1=L2
And
L={a^nb^nc^nd^nn>=678} otherwise
Choose the correct statement.
a. L is recursive
b. L is contextfree
c. We can never say anything about L as it is undecidable
d. L is regular
CHOOSE YOUR ANSWERQ12. At present it is not known if NP is closed under complementation.
Consider L defined as below
L={w wR w w in (0+1+2)* and wR is the reverse of w} if NP is closed under complement
And
L = {a^nb^nc^nd^ne^nn>=34567} otherwise
Choose the correct statement
a) L is recursive
b) L is contextfree and not contextsensitive
c) L is recursively enumerable but not recursive
d) We will be able to say something about L only after we resolve the NP complementation issue
CHOOSE YOUR ANSWERQ14. Nobody knows if P=NP at present. Consider a language L as defined below
L=(0+1)* if satisfiability is in P
L=(0*1)0* if satisfiability is not in P
L=(1*0)1* if 3sat is in P
L=(0*1*)* if 3sat is not in P
L=(0*1*0*1*)* if 0/1 knapsack problem is in P
L=(1*0*1*0*)* if 0/1 knapsack problem is not in P
L=(0*(00)*(1*11*)*) * if maxclique problem is in P
L=(0*(00)*(1*11*)*) * if nodecover problem is not in P
L=(0*1*)****(010)* if edgecover problem is not in P
L=(0* + 1* + (00)* + (11)*)*(0100101010)* if the chromatic problem is not in P
What can we say about the string 0000111100001111=x
a) x is always in L
b) whether x is in L or not will be known after we resolve P=NP
c) the definition of L is contradictory
d) x can never be in L
CHOOSE YOUR ANSWER CHOOSE YOUR ANSWERQ15. An arbitrary turing machine M will be given to you and we define a language L as follows
L=(0+00)* if M accepts at least one string
L=(0+00+000)* if M accepts at least two strings
L=(0+00+000+0000)* if M accepts at least three strings


L=(0+00+000++0^n) *if M accepts at least n1 strings
Choose the correct statement.
a) We cannot say anything about L as the question of whether a turing machine accepts a string is undecidable
b) L is contextsensitive but not regular
c) L is contextfree but not regular
d) L is not a finite set
CHOOSE YOUR ANSWERQ16. We are given two contextfree languages L1 and L2 and L defined as below
a) L=(0+1)* if L1=L2
b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2
c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1
d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable
Choose the correct statement
a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L
b) L is recursively enumerable
c) L is recursive but not contextsensitive
d) L is contextsensitive but not contextfree
e) L is contextfree but not regular
CHOOSE YOUR ANSWERQ17. It is undecidable if an arbitrary cfl is inherently ambiguous. We are given a cfg G and the language L is defined as below
L= (0+1)*01(0+1)* U 1*0* if L(G) is inherently ambiguous
L=(0+1)*10(0+1)* U 0*1* if L(G) is not inherently ambiguous
Choose the incorrect statement
a) L is regular
b) L iscontextfree
c) L is contextsensitive
d) The above choices can be resolved only if we know if L(G) is inherently ambiguous or not
CHOOSE YOUR ANSWERQ18. We are given an arbitrary turing machine M and define the language L as below
L=(0*+1*)* if M halts on blank tape
L=(0+1*)* if M ever prints a 1
L=(0*+1)* if M ever enters a designated state q
L=((0+1+00+11+000+111)+)* if M accepts an infinite set
L=0*(10*)* if M accepts a finite set
L=1*(01*)* if M accepts exactly 45 strings
Choose the correct statement with reference to the string x=00000111111000000111111
a) x is in L
b) x is not in L
c) we can never decide if x is in L as all the problems of the turing machine are undecidable
d) whether x is in L depends on the particular turing machine M
CHOOSE YOUR ANSWERQ19. We are given a language L defined as follows
L=(0+1)* if the Hamiltonian circuit problem is in P
L=(0*1*+0)* if the Traveling salesman problem is not in P
L=(0*1*1)*0* if the bin packing problem is in P
Choose the correct statement
a) the definition of L is contradictory
b) What L is will be known after we resolve the P=NP question
c) L if a finite set
d) The string 01010101001010110010101 is in L
CHOOSE YOUR ANSWERQ20. The intersection of two cfls can simulate a turing machine computation. We are given two cfls L1 and L2 and define the language L as below
a) L=(00)* if the intersection of L1 and L2 is empty
b) L=((0(00)*)(0(00)*))* if L1 is regular
c) L=(00+0000+000000)* if L2 is not regular
d) L=(00)*+(0000)* if the complement of L1 is a cfl
CHOOSE YOUR ANSWERChoose the correct statement
a) L is a finite set
b) L is a regular set
c) L is undecidable
d) L is recursive but not contextfree
CHOOSE YOUR ANSWERQ21. Nobody knows at present if P=NP.
Consider the definition of L below
L=(a^ib^jc^ki>j>k} if the sum of subsets problem is in P
L=(a^ib^jc^ki,j,k all unequal} if P is not the same as NP
Choose the correct statement
a. L is regular and not finite
b. We can tell the type of L after resolving the P=NP question
c. L is recursive and not contextfree
d. L is contextfree and not contextsensitive
CHOOSE YOUR ANSWERQ22. The regular expression 0*(10*)* denotes the same set as
a. (0*1)0* b. 0 + (0 +10)* c.*0+1)*10(0+1)* d. none of the above
CHOOSE YOUR ANSWERQ23. The regular expression 0*(10*)* denotes the same set as
a. (1*0)1* b. 0 + (0 +10)* c.*0+1)*10(0+1)* d. none of the above
[GATE 2003]
CHOOSE YOUR ANSWERQ22. The regular expression 0*(10*)* denotes the same set as
a. (0*1)1* b. 0 + (0 +10)* c.*0+1)*10(0+1)*+0*1* d. none of the above
CHOOSE YOUR ANSWERQ23. The regular expression (0+10)* denotes
a. the set of all strings not containing two consecutive 0’s
b. the set of all strings containing two consecutive 0’s
c. the set of all strings with an even number of 0’s
d. none of the above
CHOOSE YOUR ANSWERQ24. The regular expression (e +0+00)(1+10+100)* denotes
a. the set of all strings not containing three consecutive 0’s
b. the set of all strings containing three consecutive 0’s
c. the set of all strings with an odd number of 0’s
d. none of the above
CHOOSE YOUR ANSWERQ25. The regular expression (00+11+(01+10)(00+11)*(01+10))* denotes
a. the set of all strings with an even number of 0s and an even number 0’s and an even number of 1’s
b. the set of all strings over {0,1}
c. the set of all strings with the 0’s and 1’s alternating
d. none of the above
CHOOSE YOUR ANSWERQ26. If the strings of a language L can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWER[GATE 2003]
Q27. If the strings of a language L that is accepted by a turing machine can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ28. If the strings of a language L that are accepted by a multidimensional turing machine M can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ29. If the strings of a language L that are accepted by a 3 pebble machine M can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ30. If the strings of a language L that are accepted by a multitrack turing machine M can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ31. If the strings of a language L that are accepted by a nondeterminisitic, 56 pushdown tape machine M, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ32. If the strings of a language L that are accepted by a nondeterministic 987 counter machine M, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ33. If the strings of a language L that are accepted by a turing machine with 2way infinite tape, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
q) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ34. If the strings of a language L that are accepted by a 4567 headed nondeterministic turing machine,can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ35. If the strings of a language L accepted by a turing machine, which has 1000 two way infinite tapes, 1000 symbols in the tape alphabet, 2000 input symbols, l345 dimensional tapes, 34567 heads, optional 345 pushdown tapes, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ36. If the strings of a language L that are accepted by a machine which can keep 400 pebbles anywhere on its infinite input tape, but has no tape symbols, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ37. If the strings of a language L that are accepted by a turing machine, with a whose tape alphabet is a singleton set, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ38. If the strings of a language L={<M>encoding of turing machine M}, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ39. If the strings of a language L ={<M>encoding of 45678 push down tape machines} can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ40. If the strings of a language L={<M> M is an encoding of turing machines, pushdown automata, linear bounded automata, finite automata}, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ41. If the strings of a language L ={<M> M is an encoding of turing machines that have more than 34567890 states}, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
CHOOSE YOUR ANSWERQ42. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà aSbSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWER
Q43. Let G=({S},{a,b,c},R,S) be a contextfree grammar where the rule set is
Sà aSabSbc.
Which of the following statements is true?
a) G is ambiguous
b) There exist x and y in L(G) such that xy is in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ44. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà aSbSSSSSSSSSSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ45. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà aSbaaSbbSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ46. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà aaSbbSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ47. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà aaaSbbbSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ48. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà abSbaSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ49. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà aaabaaaSbbbabbbSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ50. Choose the correct statement for the language L={a^nb^nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
c) L is regular
d) There exists a deterministic two way finite automata accepting L
CHOOSE YOUR ANSWERQ51. Choose the correct statement for the language L={a^100nb^100nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
c) L is regular
d) There exists a deterministic two way finite automata accepting L
CHOOSE YOUR ANSWERQ52. Choose the correct statement for the language L={(aaabaaa)^1000n(bbbbbbb)^34567nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
c) L is regular
d) There exists a deterministic two way finite automata accepting L
CHOOSE YOUR ANSWERQ53. Choose the correct statement for the language L={"("^n " )" ^nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
c) L is regular
d) There exists a deterministic two way finite automata accepting L
CHOOSE YOUR ANSWERQ54. Choose the correct statement for the language L={(begin)^n(end)^nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
c) L is regular
d) There exists a deterministic two way finite automata accepting L
CHOOSE YOUR ANSWERQ55. Let G=({S},{a,b},R,S) be a contextfree grammar where the rule set is
Sà aSbSSe
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) L(G) is the set of all strings of balanced parenthesis with a as the opening parenthesis and b as the closing parenthesis.
d) We can find a deterministic finite state automaton that accepts L(G)
CHOOSE YOUR ANSWERQ56. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 finite
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is recursive
CHOOSE YOUR ANSWERQ57. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 finite
b) L1e NP and L2e PSPACE
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is contextsensitive
CHOOSE YOUR ANSWERQ58. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 regular
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is contextsensitive and L2 is recursive
CHOOSE YOUR ANSWERQ59. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e PSPACE and L2 e DSPACE(n^1000)
b) L1e NP and L2e DTIME(2^1000n)
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is accepted by a 2PDA
CHOOSE YOUR ANSWERQ60. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 is accepted by a 2NFA
b) L1e NP and L2is accepted by a linear bounded automata
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is accepted by a turing machine that halts on all inputs
CHOOSE YOUR ANSWERQ61. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 is accepted by a deterministic push down automata
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is accepted by a deterministic linear bounded automata
CHOOSE YOUR ANSWERQ62. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e PSPACE and L2 is in NSPACE(2^2^2^2^n)
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is finite
CHOOSE YOUR ANSWERQ63. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 is finite and L2 is contextfree
b) L1e NP and L2e NP
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is recursive
CHOOSE YOUR ANSWERQ64. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 finite
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is recursive
CHOOSE YOUR ANSWERQ65. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e contextfree and L2 regular but not finite
b) L1e NP and L2 is accepted by a deterministic turing machine
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is recursive but not contextsensitive
CHOOSE YOUR ANSWERQ66. Consider two languages L1 and L2 each on the alphabet S . Let f: S >S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^1 be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 is finite but not necessarily regular and L2 is contextfree but not necessarily contextsensitive
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is recursive but not necessarily contextsensitive
CHOOSE YOUR ANSWERQ67. Define languages L0 and L1 as follows:
L0={<M,w,0>M halts on w}
L1={<M,w,1> M does not halt on w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component w, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ68. Define languages L0 and L1 as follows:
L0={<M,0>M halts}
L1={<M,1> M does not halt }
Here <M,I> is a pair whose first component, M is an encoding of a turing machine starting with blank tape, second component is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ69. Define languages L0 and L1 as follows:
L0={<M,w,0>M halts on w}
L1={<M,w,1> M does not halt on w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a 1200 push down tape machine , second component w, is a string representing the input, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ70. Define languages L0 and L1 as follows:
L0={<M,0>M accepts at least two strings}
L1={<M,1> M does not accept at least two strings}
Here <M,I> is a pair, whose first component, M is an encoding of a turing machine , second component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ71. Define languages L0 and L1 as follows:
L0={<M,0>M accepts an infinite set}
L1={<M,1> M does not accept an infinite set}
Here <M,I> is a pair, whose first component, M is an encoding of a turing machine , second component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ72. Define languages L0 and L1 as follows:
L0={<M,w,0>M halts on w}
L1={<M,w,1> M does not halt on w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a three counter machine machine , second component w is a triplet giving the initial position of the pebbles, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ73. Define languages L0 and L1 as follows:
L0={<P,w,0>P halts on w}
L1={<P,w,1> P does not halt on w}
Here <P,w,I> is a triplet, whose first component, P is an encoding of a C++ program, second component w, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ74. Define languages L0 and L1 as follows:
L0={<Q,w,0>Q halts on w}
L1={<Q,w,1> Q does not halt on w}
Here <Q,w,I> is a triplet, whose first component, Q is an encoding of a java program, second component w, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ75. Define languages L0 and L1 as follows:
L0={<M,w,0>M halts on w}
L1={<M,w,1> M does not halt on w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a multidimentsional, multiheaded, multitape turing machine , second component w, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ76. Define languages L0 and L1 as follows:
L0={<M,w,0>M halts on w}
L1={<M,w,1> M does not halt on w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ77. Define languages L0 and L1 as follows:
L0={<M,w,0>M accepts on w}
L1={<M,w,1> M does not accept w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component w, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ78. Define languages L0 and L1 as follows:
L0={<P,w,0>P halts on input w}
L1={<P,w,1> P loops on input w}
Here <P,w,I> is a triplet, whose first component, P is an encoding of a C program, second component w, is a string and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ79. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a turing machine, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ80. Define languages L0 and L1 as follows:
L0={<M,M1,0>M accepts a subset of what is accepted by M1}
L1={<M,M1,1> M does not accept a subset of what is accepted by M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a turing machine, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ81. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a pushdown automaton machine, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ82. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a halting turing machine, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWER
Q83. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a finite automaton machine, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ84. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a deterministic pushdown automaton, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWER
Q85. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a deterministic linear bounded atuomaton and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWER
Q86. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a nondeterministic linear bounded automaton, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ87. Define languages L0 and L1 as follows:
L0={<M,M1,0>M is equivalent to M1}
L1={<M,M1,1> M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a 100 tape nondeterministic turing machine that halts on all inputs, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWER
Q88. Define languages L0 and L1 as follows:
L0={<M,w,0>M in the course of its computation visits state w}
L1={<M,w,1> M does not halt visit state w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a state and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d)Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ89. Define languages L0 and L1 as follows:
L0={<M,w,0>M prints symbol w}
L1={<M,w,1> M never prints symbol w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a symbol and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L’ is not
(b) L’ is recursively enumerable but L is not
(c) Both L and L’ are recursive
(d)Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ90. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0,1, B} and its input alphabet is (0,1). The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table
0 
1 
B 

q0 
q1,1,R 
q1,1,R 
Halt 
q1 
q1,1,R 
q0,1,L 
q0,B,L 
The table is interpreted as illustrated below.
The entry (q1,1,R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square and moves its tape head one position to the right and transitions to state q1.
Which of the following statements is true about M?
(a) M does not halt on any string in (0+1)+
(b) M does not halt on any string in (00+1)*
(c) M halts on all strings ending in a 0
(d) M halts on all strings ending in a 1
CHOOSE YOUR ANSWERQ90. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0,1, B} and its input alphabet is (0,1). The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table
1 
0 
B 

q0 
q1,0,R 
q1,0,R 
Halt 
q1 
q1,0,R 
q0,0,L 
q0,B,L 
The table is interpreted as illustrated below.
The entry (q1,1,R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square and moves its tape head one position to the right and transitions to state q1.
Which of the following statements is true about M?
(a) M does not halt on any string in (0+1)+
(b) M does not halt on any string in (0+11)*
(c) M halts on all strings ending in a 0
(d) M halts on all strings ending in a 1
CHOOSE YOUR ANSWERQ90. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0,1, B} and its input alphabet is (0,1). The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table
0 
1 
B 

q0 
q1,1,R 
q1,1,R 
Halt 
q1 
q1,1,R 
q0,1,L 
q0,B,L 
The table is interpreted as illustrated below.
The entry (q1,1,R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square and moves its tape head one position to the right and transitions to state q1.
Which of the following statements is false about M?
(a) M halts on any string in (0+1)+
(b) M halts on any string in (00+1)*
(c) M does not halt on all strings ending in a 0
(d) M does not halt on all strings ending in a 1
CHOOSE YOUR ANSWERQ91. Consider the following deterministic finite state automaton M.
Let S denote the set of all seven bit binary strings in which the first, the fourth and the last bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 5 (c) 7 (d) 8
CHOOSE YOUR ANSWER
Q92. Consider the finite state automaton given below
0 
1 

A 
b 
a 
B 
c 
a 
C 
c 
d 
*D 
d 
d 
Let S denote the set of all seven bit binary strings in which the first, the fourth and the last bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 5 (c) 7 (d) 8
CHOOSE YOUR ANSWER
Q92. Consider the finite state automaton given below
1 
0 

A 
b 
a 
B 
c 
a 
C 
c 
d 
*D 
d 
D 
Let S denote the set of all seven bit binary strings in which the first, the fourth and the last bits are 0. The number of strings in S that are accepted by M is
(a) 1 (b) 5 (c) 7 (d) 8
CHOOSE YOUR ANSWERQ93. Consider the finite state automaton given below
0 
1 

A 
b 
a 
B 
c 
a 
C 
c 
d 
*D 
d 
d 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) 8
CHOOSE YOUR ANSWERQ94. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
*D 
D 
d 
The following can be said about the set accepted by the finite automata
a) 001 is compulsorily a substring in the language accepted
b) 011 is compulsorily a substring in thelanguage accepted
c) 0* is in the language accepted by the finite auotmata
d) 11 is compulsorily as substring of any string in the language accepted
CHOOSE YOUR ANSWER
Q95. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
*D 
D 
d 
Let S denote the set of all five bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) 8
CHOOSE YOUR ANSWERQ96. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
*D 
D 
d 
Choose the correct statement
a) the head of any string accepted is from the language set of all strings over (0+1)* not containing two consecutive 1’s
b) the set (0+1)* is accepted by the finite automata
c) the set 001(0+1)* is the language accepted by the finite auotomata
d) any string accepted has an odd no of 0’s
CHOOSE YOUR ANSWERQ96. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
*D 
D 
d 
Choose the correct statement
a) the set of all strings with an odd number of 0’s(except 0) , followed by a 1 is accepted by the finite automata
b) the set (0+1)* is accepted by the finite automata
c) the set 001(0+1)* is the language accepted by the finite auotomata
d) any string accepted has an odd no of 0’s
CHOOSE YOUR ANSWERQ97. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
*D 
D 
d 
Let S denote the set of all four bit binary strings. The number of strings in S that are accepted by M is
(a) 1 (b) 3 (c) 7 (d) 8
CHOOSE YOUR ANSWERQ98. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
*D 
D 
d 
Let S denote the set of all three. The number of strings in S that are accepted by M is
(a) 1 (b) 5 (c) 7 (d) 8
CHOOSE YOUR ANSWERQ99. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
*d 
D 
d 
Let S denote the set of all two bit strings. The number of strings in S that are accepted by M is
(a) 1 (b) 5 (c) 7 (d) 0
CHOOSE YOUR ANSWERQ100. Consider the finite state automaton given below
0 
1 

A 
B 
a 
B 
C 
a 
C 
C 
d 
D 
D 
d 
Let S denote the set of all one binary strings. The number of strings in S that are accepted by M is
(a) 1 (b) 5 (c) 7 (d) 0
CHOOSE YOUR ANSWERQ101. Consider the finite automaton given below
0 
1 

à q0 
j 
q1 
q1 
Q0 
q1 
The set accepted by the finite automata can be denoted by the regular expression
a) (0+1)*00
b) (0+1)*00(0+1)*
c) the complement of (0+1)*00(0+1)*
d) (0+1)*
CHOOSE YOUR ANSWERQ102. Consider the finite automaton given below
0 
1 

à q0 
j 
q1 
q1 
Q0 
q1 
The minimal finite automata corresponding to the above automaton has
a) 2 states b) 3 states d) 1 state d) no states
CHOOSE YOUR ANSWERQ103. Consider the finite automaton given below
0 
1 

à q0 
j 
q1 
q1 
Q0 
q1 
The set accepted by the above finite automaton is
a) the set of all strings not containing two consecutive 0’s
b) the set of all strings containing two consecutive 0’s
c) the set of all strings not containing a 0
d) the set of all strings containing a 1
CHOOSE YOUR ANSWERQ104. Consider the finite automaton given below
0 
1 

à q0 
j 
q1 
q1 
Q0 
q1 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ105. Consider the finite automaton given below
0 
1 

à q0 
j 
q1 
Q1 
Q0 
q1 
Let M1 be the machine obtained by interchanging the final and nonfinal states of the above automaton. The set accepted by M1 is
a) the set of all strings containing two consecutive 0’s
b) the set of all strings no containing two consecutive 0’s
c) the set (0+1)*
d) the set of all strings not containing a 1
CHOOSE YOUR ANSWERQ106. Consider the finite automaton given below
0 
1 

à *q0 
q00 
q1 
*q1 
q0 
q1 
*q00 
j 
q1 
The minimal finite automata corresponding to the above automaton has
a) 3 states b)4 states c) 5 states d) 6 states
CHOOSE YOUR ANSWERQ107. Consider the finite automaton given below
0 
1 

à *q0 
q00 
q1 
*q1 
q0 
q1 
*q00 
j 
q1 
The regular expression denoting the set accepted by the above finite automaton is
a) complement of (0+1)*000(0+1)*
b) (0+1)*000(0+1)*
c) (0+1)*
d) (0+1)+
CHOOSE YOUR ANSWERQ108. Consider the finite automaton given below
0 
1 

à *q0 
q00 
q1 
*q1 
q0 
q1 
*q00 
j 
q1 
The set accepted by the above finite automaton is best described as
a) the set of all strings over {0,1} not containing three consecutive 0’s
b) the set of all strings over {0,1} containing three consecutive 0’s
c) the set of all strings over {0,1}
d) the set of all strings over {0,1} not containing two consecutive 1’s
CHOOSE YOUR ANSWERQ109. Consider the finite automaton given below
0 
1 

à *q0 
q00 
q1 
*q1 
q0 
q1 
*q00 
j 
q1 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ110. Consider the finite automaton given below
0 
1 

à *q0 
q00 
q1 
*q1 
q0 
q1 
*q00 
j 
q1 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 that are accepted by a machine M obtained by interchanging the final and nonfinal states of the finite automaton given above. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWER
Q111. Consider the finite automaton given below

0 
1 
>qs 
j 
q1 
*q0 
q0 
q1 
q1 
q2 
q3 
q2 
q4 
q0 
q3 
q1 
q2 
q4 
q3 
q4 
The set accepted by the above finite automaton can be described as
a) the set of all strings over {0,1} that starting with a 1 and interpreted as the binary representation of an integer are congruent to 0 modulo 5.
b) The set of all strings over {0,1}
c) The set of all strings over {0,1} that interpreted as the binary representation of an integer are congruent to 0 modulo 5
d) The set of all strings over {0,1}not containing a 0
CHOOSE YOUR ANSWERQ112. Consider the finite automaton given below

0 
1 
>qs 
j 
q1 
*q0 
q0 
q1 
q1 
q2 
q3 
q2 
q4 
q0 
q3 
q1 
q2 
q4 
q3 
q4 
The minimal finite automaton corresponding to the above machine has
a) 7 states
b) 6 states
c) 5 states
d) 8 states
CHOOSE YOUR ANSWERQ113. Consider the finite automaton given below

0 
1 
>qs 
j 
q1 
*q0 
q0 
q1 
Q1 
q2 
q3 
Q2 
q4 
q0 
Q3 
q1 
q2 
Q4 
q3 
q4 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 that are accepted by a machine M obtained by interchanging the final and nonfinal states of the finite automaton given above. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ114. Consider the finite automaton given below

0 
1 
>qs 
j 
q1 
*q0 
q0 
q1 
Q1 
q2 
q3 
Q2 
q4 
q0 
Q3 
q1 
q2 
Q4 
q3 
q4 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ115. Consider the finite automaton given below
0 
1 

>Q0 
Q0 
Q1 
Q1 
Q0 
Q11 
Q11 
Q0 
Q111 
*q111 
Q111 
Q111 
The minimal finite automat corresponding to the above automaton has
a) 3 states b)4 states c) 5 states d) none of the above
CHOOSE YOUR ANSWERQ116. Consider the finite automaton given below
0 
1 

>Q0 
Q0 
Q1 
Q1 
Q0 
Q11 
Q11 
Q0 
Q111 
*q111 
Q111 
Q111 
The regular expression denoting the set accepted by the above finite automaton is
a) (0+1)*111
b) (0+1)*111(0+1)*
c) complement of (0+1)*111(0+1)*
d) complement of (0+1)*111
CHOOSE YOUR ANSWERQ117. Consider the finite automaton given below
0 
1 

>Q0 
Q0 
Q1 
Q1 
Q0 
Q11 
Q11 
Q0 
Q111 
*q111 
Q111 
Q111 
The set accepted by the above automaton is, over the alphabet {0,1}
a) the set of all strings containing three consecutive 1’s
b) the set of all strings not containing three consecutive 1’s
c) the set of all strings containing three consecutive 0’s
d) the set of all strings ending in three consecutive 1’s
CHOOSE YOUR ANSWERQ118. Consider the finite automaton given below
0 
1 

>Q0 
Q0 
Q1 
Q1 
Q0 
Q11 
Q11 
Q0 
Q111 
*q111 
Q111 
Q111 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ119. Consider the finite automaton given below
0 
1 

>Q0 
Q0 
Q1 
Q1 
Q0 
Q11 
Q11 
Q0 
Q111 
*q111 
Q111 
Q111 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above automaton. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ120. Consider the finite automaton given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Qs 
j 
Q0 
j 
Qs 
The set accepted by the finite automata over the alphabet {0,1} can be described as
a) the set of all strings over {0,1}
b) the set of all strings over {0,1} where every prefix does not have one more 0 then 1’s nor one more 1 than 0’s.
c) the set of all strings over {0,1} where every prefix has one more 1 than 0’s or one more 0 than 1’s
d) none of the above
CHOOSE YOUR ANSWERQ121. Consider the finite automaton given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Qs 
j 
Q0 
j 
Qs 
The regular expression denoting the set accepted by the above automaton is
a) (01+10)*
b) (0+1)*
c) (00+11)*
d) none of the above
CHOOSE YOUR ANSWERQ122. Consider the finite automaton given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Qs 
j 
Q0 
j 
Qs 
The minimal finite automata corresponding to the above machine has
a) 3 states
b) 4 states
c) 5 states
d) 6 states
CHOOSE YOUR ANSWER
Q123. Consider the finite automaton given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Qs 
j 
Q0 
j 
Qs 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above automaton. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ124. Consider the finite automaton given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Qs 
j 
Q0 
j 
Qs 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ125. Consider the finite automaton given below
0 
1 

>*Qs 
Qs 
Q1 
*q1 
Qs 
Q11 
*Q11 
Q11,0 
Q11 
*Q11,0 
j 
Q11 
The set accepted by the above automaton can be best described as
a) the set of all strings over {0,1} where every pair of consecutive 0’s occurs before any pair of adjacent 1’s
b) the set of all strings over {0,1} where every pair of adjacent 1’s occurs before any pair of adjacent 0’s
c) the set of all strings over {0,s}
d) none of the above
CHOOSE YOUR ANSWERQ126. Consider the finite automaton given below
0 
1 

>*Qs 
Qs 
Q1 
*q1 
Qs 
Q11 
*Q11 
Q11,0 
Q11 
*Q11,0 
j 
Q11 
The minimal finite automata corresponding to the above automaton has
a) 4 states b) 5 states c) 6 states d) none of the above
CHOOSE YOUR ANSWERQ127. Consider the finite automaton given below
0 
1 

>*Qs 
Qs 
Q1 
*q1 
Qs 
Q11 
*Q11 
Q11,0 
Q11 
*Q11,0 
j 
Q11 
The minimal finite auotmata accepting the complement of the language accepted by the above finite auotomaton has
a) 3 states b)4 states c) 5 states d) none of the above
CHOOSE YOUR ANSWERQ128. Consider the finite automaton given below
0 
1 

>*Qs 
Qs 
Q1 
*q1 
Qs 
Q11 
*Q11 
Q11,0 
Q11 
*Q11,0 
j 
Q11 
The regular expression denoting the set accepted by the above automaton can be best described as
a) (01+0)*(1+10)*
b) (10+0)*(0+10)*
c) (0+1)*
d) none of the above
CHOOSE YOUR ANSWERQ129. Consider the finite automaton given below
0 
1 

>*Qs 
Qs 
Q1 
*q1 
Qs 
Q11 
*Q11 
Q11,0 
Q11 
*Q11,0 
j 
Q11 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ130. Consider the finite automaton given below
0 
1 

>*A 
A 
A,B 
B 
C 
C 
C 
D 
D 
*D 
j 
j 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ131. Consider the finite automaton given below
0 
1 

>*A 
A 
A,B 
B 
C 
C 
C 
D 
D 
*D 
j 
j 
Let the above machine M accept the language L. Consider the machine M1 obtained by interchanging the final and nonfinal states of the above machine and accepting the language L1. Which of the following is correct?
a) L1 is a subset of L
b) L1=L
c) L1 is the complement of L
d) L1=(0+1)*
CHOOSE YOUR ANSWERQ132. Consider the finite automaton given below
0 
1 

>*A 
A 
A,B 
B 
C 
C 
C 
D 
D 
*D 
j 
j 
The minimal dfa for the above automaton has
a) 6 states
b) 7 states
c) 8 states
d) 10 states
CHOOSE YOUR ANSWERQ133. Consider the finite automaton given below
0 
1 

>*A 
A 
A,B 
B 
C 
C 
C 
D 
D 
*D 
j 
j 
The language accepted by the above machine is best described as
a) the set of all strings over {0,1} where the third symbol from the right end is a 1
b) the set of all strings over {0,1} where the third symbol from the right end is a 0
c) the set of all strings over {0,1}*
d) the set of all strings with an even number of 0’s
CHOOSE YOUR ANSWER
Q134.Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Qs 
Q0 
Q00 
Qs 
*Q00 
Q00 
Qs 
The minimal finite automata corresponding to the above automaton has
a) 3 states b)4 states c)5 states d) none of the above
CHOOSE YOUR ANSWERQ135.Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Qs 
Q0 
Q00 
Qs 
*Q00 
Q00 
Qs 
The minimal finite automata accepting the complement of the set accepted by the above automaton has
a) 3 state b) 4 states c) 5 states d) none of the above
CHOOSE YOUR ANSWERQ136.Consider the finite automaton given below
0 
1 

>*Qs 
Q0 
Qs 
Q0 
Q00 
Qs 
*Q00 
Q00 
Qs 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ137.Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Qs 
Q0 
Q00 
Qs 
*Q00 
Q00 
Qs 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ138.Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Qs 
Q0 
Q00 
Qs 
*Q00 
Q00 
Qs 
The language accepted by the above automaton can be described as
a) the set of all strings over {0,1} ending in 00
b) the set of all strings over {0,1}
c) the set of all strings ending with a 0
d) the set of all strings over {0,1} ending with a 1
CHOOSE YOUR ANSWERQ139. Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q1 
*Q11 
Q0 
Q11 
The set accepted by the finite automata can be described as
a) the set of all strings over {0,1} ending in 00 or 11
b) the set of all strings over {0,1} not ending in 00 or 11
c) the set of all strings over {0,1}
d) none of the above
CHOOSE YOUR ANSWERQ140. Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q1 
*Q11 
Q0 
Q11 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ141. Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q1 
*Q11 
Q0 
Q11 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ142. Consider the finite automaton given below
0 
1 

>Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q1 
*Q11 
Q0 
Q11 
The minimal finite automata corresponding to the above machine has
a) 2 states
b) 3 states
c) 4 states
d) 5 states
CHOOSE YOUR ANSWERQ143. Consider the finite automaton given below
0 
1 

>*Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q00 
*Q11 
Q11 
Q11 
The language accepted by the above finite automaton can be described as
a) the set of all strings containing 00 or 11 as a substring
b) the of all strings over {0,1} ending in 00 or 11
c) the set of all strings over {0,1}
d) none of the above
CHOOSE YOUR ANSWERQ144. Consider the finite automaton given below
0 
1 

>*Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q00 
*Q11 
Q11 
Q11 
The minimal finite automata accepting the same language as the above machine has
a) 3 states
b) 5 states
c) 6 states
d) none of the above
CHOOSE YOUR ANSWERQ145. Consider the finite automaton given below
0 
1 

>*Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q00 
*Q11 
Q11 
Q11 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ146. Consider the finite automaton given below
0 
1 

>*Qs 
Q0 
Q1 
Q0 
Q00 
Q1 
Q1 
Q0 
Q11 
*Q00 
Q00 
Q00 
*Q11 
Q11 
Q11 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ147. Consider the finite automaton given below
0 
1 

>*Q00 
Q10 
Q01 
Q10 
Q00 
Q11 
Q01 
Q11 
Q00 
Q11 
Q01 
Q10 
The minimal finite automata accepting the same language as the machine above has
a) 4 states
b) 5 states
c) 3 states
d) 6 states
CHOOSE YOUR ANSWERQ148. Consider the finite automaton given below
0 
1 

>*Q00 
Q10 
Q01 
Q10 
Q00 
Q11 
Q01 
Q11 
Q00 
Q11 
Q01 
Q10 
The set accepted by the above automaton can be denoted by the regular expression
a)(0+1)*
b)(00+11)*
c)(00+11+(01+10)(00+11)*(01+10))*
d)none of the above
CHOOSE YOUR ANSWERQ149. Consider the finite automaton given below
0 
1 

>*Q00 
Q10 
Q01 
Q10 
Q00 
Q11 
Q01 
Q11 
Q00 
Q11 
Q01 
Q10 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ150. Consider the finite automaton given below
0 
1 

>*Q00 
Q10 
Q01 
Q10 
Q00 
Q11 
Q01 
Q11 
Q00 
Q11 
Q01 
Q10 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ151. Consider the finite automaton given below
0 
1 

>*A 
A 
B 
*B 
C 
B 
C 
C 
C 
The set accepted by the above automaton can be best described as
a) (0+1)*
b) 0*1*
c) 0*1+
d) (0*11*)*
CHOOSE YOUR ANSWERQ152. Consider the finite automaton given below
0 
1 

>*A 
A 
B 
*B 
C 
B 
C 
C 
C 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ153. Consider the finite automaton given below
0 
1 

>*A 
A 
B 
*B 
C 
B 
C 
C 
C 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ154. Consider the finite automaton given below
0 
1 

>*A 
A 
B 
*B 
C 
B 
C 
C 
C 
The minimal finite automata corresponding to the above automaton has
a) 3 states
b) 4 states
c) 5 states
d) none of the above
CHOOSE YOUR ANSWERQ155. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Qs 
Q1 
The languages accepted by the above automaton can be best described as
a) one or more repetititons of the string: the set of all strings ending in 101
b) one or more repetititons of the string: the set of all strings ending in 101 and having only one occurrence of 101
c) the set of all strings over {0,1}
d) none of the above
CHOOSE YOUR ANSWERQ156. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Qs 
Q1 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ157. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Qs 
Q1 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ158. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Qs 
Q1 
The minimal finite automata corresponding to the above automaton has
a) 3 states
b) 4 states
c) 5 states
d) 6 states
CHOOSE YOUR ANSWERQ159. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Q10 
Q1 
The set accepted by the above automata can be described as
a) the set of all strings over {0,1} ending in 101
b) the set of all strings over {0,1} not ending in 101
c) the set of all strings over {0,1}
d) none of the above
CHOOSE YOUR ANSWERQ160. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Q10 
Q1 
The minimal finite automata corresponding to the above machine has
a) 4 states
b) 5 states
c) 3 states
d) 6 states
CHOOSE YOUR ANSWERQ161. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Q10 
Q1 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ162. Consider the finite automata given below
0 
1 

>Qs 
Qs 
Q1 
Q1 
Q10 
Q1 
Q10 
Qs 
Q101 
*Q101 
Q10 
Q1 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ163. Consider the nfa M given below
0 
1 

>A 
B,D 
D 
*B 
 
 
C 
C 
C,D 
D 
C,D 
A,D 
Let L be the language accepted by M. Let L1 be the language accepted by M1 where M1 is obtained from M by interchanging the final and nonfinal states of M
Choose the correct answer
a) L1 is the complement of L
b) L1 is a subset of L
c) L1=L
d) L1=(0+1)*
CHOOSE YOUR ANSWERQ164. Consider the nfa below
0 
1 

>A 
B,C 
D 
B 
A,B 
B,C 
*C 
C 
C 
*D 
D 
D 
Let L be the language accepted by M. Let L1 be the language accepted by M1 where M1 is obtained from M by interchanging the final and nonfinal states of M
Choose the correct answer
a) L1 is the complement of L
b) L1 is a subset of L
c) L1=L
d) L1=(0+1)*
CHOOSE YOUR ANSWERQ165. Consider the nfa given below
0 
1 

>A 
A 
A,B 
B 
C 
C 
C 
D 
D 
*D 
 
 
Let L be the language accepted by M. Let L1 be the language accepted by M1 where M1 is obtained from M by interchanging the final and nonfinal states of M
Choose the correct answer
a) L1 is the complement of L
b) L1 is a subset of L
c) L1=L
d) L1=(0+1)*
CHOOSE YOUR ANSWERQ166. Consider the nfa given below
0 
1 

>A 
A,B 
A,D 
B 
C 
 
*C 
 
 
D 
 
E 
*E 
 
 
Let L be the language accepted by M. Let L1 be the language accepted by M1 where M1 is obtained from M by interchanging the final and nonfinal states of M
Choose the correct answer
a) L1 is the complement of L
b) L1 is a subset of L
c) L1=L
d) L1=(0+1)*
CHOOSE YOUR ANSWERQ167. Consider the nfa given below
0 
1 

>A 
A,B 
A 
B 
C 
 
C 
D 
 
*D 
 
 
Let L be the language accepted by M. Let L1 be the language accepted by M1 where M1 is obtained from M by interchanging the final and nonfinal states of M
Choose the correct answer
a) L1 is the complement of L
b) L1 is a subset of L
c) L1=L
d) L1=(0+1)*
CHOOSE YOUR ANSWERQ168. Consider the nfa given below
0 
1 

>A 
A,B 
A 
B 
C 
 
*C 
 
 
Let L be the language accepted by M. Let L1 be the language accepted by M1 where M1 is obtained from M by interchanging the final and nonfinal states of M
Choose the correct answer
a) L1 is the complement of L
b) L1 is a subset of L
c) L1=L
d) L1=(0+1)*
CHOOSE YOUR ANSWERQ169. Consider the nfa M given below
0 
1 

>A 
B,D 
D 
*B 
 
 
C 
C 
C,D 
D 
C,D 
A,D 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ170. Consider the nfa M given below
0 
1 

>A 
B,D 
D 
*B 
 
 
C 
C 
C,D 
D 
C,D 
A,D 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ171. Consider the nfa below
0 
1 

>A 
B,C 
D 
B 
A,B 
B,C 
*C 
C 
C 
*D 
D 
D 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ172. Consider the nfa below
0 
1 

>A 
B,C 
D 
B 
A,B 
B,C 
*C 
C 
C 
*D 
D 
D 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWER173. Consider the nfa given below
0 
1 

>A 
A 
A,B 
B 
C 
C 
C 
D 
D 
*D 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWER174. Consider the nfa given below
0 
1 

>A 
A 
A,B 
B 
C 
C 
C 
D 
D 
*D 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ175. Consider the nfa given below
0 
1 

>A 
A,B 
A,D 
B 
C 
 
*C 
 
 
D 
 
E 
*E 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ176. Consider the nfa given below
0 
1 

>A 
A,B 
A,D 
B 
C 
 
*C 
 
 
D 
 
E 
*E 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M.The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ177. Consider the nfa given below
0 
1 

>A 
A,B 
A 
B 
C 
 
C 
D 
 
*D 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ178. Consider the nfa given below
0 
1 

>A 
A,B 
A 
B 
C 
 
C 
D 
 
*D 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ179. Consider the nfa given below
0 
1 

>A 
A,B 
A 
B 
C 
 
*C 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states in the above machine. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ180. Consider the nfa given below
0 
1 

>A 
A,B 
A 
B 
C 
 
*C 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ181. Consider the 2DFA given below
0 
1 

>*Q0 
(Q1,R) 
(Q1,L) 
*Q1 
(Q0,R) 
(Q0,L) 
Choose the correct statement
a) the machine accepts all strings ending with a 1
b) the machine accepts 0*
c) the machine accepts 01
d) the machine accepts 001
CHOOSE YOUR ANSWERQ182. Consider the 2DFA given below
0 
1 

>*Q0 
(Q1,R) 
(Q1,L) 
*Q1 
(Q0,R) 
(Q0,L) 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ183. Consider the 2DFA given below
0 
1 

>*Q0 
(Q1,R) 
(Q1,L) 
*Q1 
(Q0,R) 
(Q0,L) 
Choose the false statement
a) the machine loops on 01
b) the machine does not accept 0000
c) the machine accepts strings ending with a 1
d) the machine accepts strings ending with 10
CHOOSE YOUR ANSWERQ184. Consider the 2DFA given below
0 
1 

>*Q0 
(Q0,R) 
(Q1,R) 
*Q1 
(Q0,L) 
(Q2,L) 
*Q2 
(Q1,L) 
(Q1,L) 
Choose the correct statement
a) the machine accepts all strings ending with a 1
b) the machine accepts 0*
c) the machine accepts 01
d) the machine accepts 001
CHOOSE YOUR ANSWERQ185. Consider the 2DFA given below
0 
1 

>*Q0 
(Q0,R) 
(Q1,R) 
*Q1 
(Q0,L) 
(Q2,L) 
*Q2 
(Q1,L) 
(Q1,L) 
Choose the false statement
a) the machine loops on 01
b) the machine does not accept 0000
c) the machine accepts strings ending with a 1
d) the machine accepts strings ending with 10
CHOOSE YOUR ANSWERQ186. Consider the 2DFA given below
0 
1 

>*Q0 
(Q0,R) 
(Q1,R) 
*Q1 
(Q0,L) 
(Q2,L) 
*Q2 
(Q1,L) 
(Q1,L) 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ187. Consider the 2NFA given below
0 
1 

>*Q0 
{(Q0,R)} 
{(q0,L),(q1,R)} 
*Q1 
{(Q1,L)} 
{(Q1,L)} 
Choose the correct statement
a) the machine accepts all strings ending with a 1
b) the machine accepts 0*
c) the machine accepts 01
d) the machine accepts 001
CHOOSE YOUR ANSWERQ189. Consider the 2NFA given below
0 
1 

>*Q0 
{(Q0,R)} 
{(q0,L),(q1,R)} 
*Q1 
{(Q1,L)} 
{(Q1,L)} 
Choose the false statement
a) the machine loops on 01
b) the machine does not accept 0000
c) the machine accepts strings ending with a 1
d) the machine accepts strings ending with 10
CHOOSE YOUR ANSWERQ190. Consider the 2NFA given below
0 
1 

>*Q0 
{(Q0,R)} 
{(q0,L),(q1,R)} 
*Q1 
{(Q1,L)} 
{(Q1,L)} 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ191. Consider the turing machine M defined below
0 
1 
B 

>Q0 
(Q0,0,R) 
(Q2,1,L) 
(Qf,,) 
Q1 
(Q2,1,L) 
(Q1,1,R) 
(Qf,,) 
Q2 
(Q2,1,L) 
(Q2,0,L) 
(Qf,,) 
*Qf 
 
 
 
Choose the correct statement
a) the machine accepts all strings ending with a 1
b) the machine accepts 0*
c) the machine accepts 01
d) the machine accepts 001
CHOOSE YOUR ANSWERQ192. Consider the turing machine M defined below
0 
1 
B 

>Q0 
(Q0,0,R) 
(Q2,1,L) 
(Qf,,) 
Q1 
(Q2,1,L) 
(Q1,1,R) 
(Qf,,) 
Q2 
(Q2,1,L) 
(Q2,0,L) 
(Qf,,) 
*Qf 
 
 
 
Choose the false statement
a) the machine loops on 01
b) the machine does not accept 0000
c) the machine accepts strings ending with a 1
d)the machine accepts strings ending with 10
CHOOSE YOUR ANSWERQ193. Consider the turing machine M defined below
0 
1 
B 

>Q0 
(Q0,0,R) 
(Q2,1,L) 
(Qf,,) 
Q1 
(Q2,1,L) 
(Q1,1,R) 
(Qf,,) 
Q2 
(Q2,1,L) 
(Q2,0,L) 
(Qf,,) 
*Qf 
 
 
 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ194. Consider the turing machine M given below
@ 
0 
1 
$ 

>Q0 
{(Q0,@,R)} 
{(Q0,0,R),(Q1,0,R)} 
{(Q0,1,r),(Q1,1,r)} 
{(Q2,$,L)} 
Q1 
{(Q0,@,R)} 
{(Q0,0,R),(Q1,0,R)} 
{(Q0,1,r),(Q1,1,r)} 
{(Q2,$,L)} 
Q2 
HALT 
{(Q2,1,L)} 
{(q2,0,L)} 
 
Choose the correct statement
a) the machine is guaranteed to halt on all inputs
b) there exists an input for which it halts
c) it is undecidable if the above machine will halt
d) the machine does not accept a contextsensitive language
CHOOSE YOUR ANSWERQ195. Consider the turing machine M given below
@ 
0 
1 
$ 

>Q0 
{(Q0,@,R)} 
{(Q0,0,R),(Q1,0,R)} 
{(Q0,1,r),(Q1,1,r)} 
{(Q2,$,L)} 
Q1 
{(Q0,@,R)} 
{(Q0,0,R),(Q1,0,R)} 
{(Q0,1,r),(Q1,1,r)} 
{(Q2,$,L)} 
Q2 
HALT 
{(Q2,1,L)} 
{(q2,0,L)} 
 
Choose the correct statement
a) the machine complements the input over {0,1}and halts
b) the machine does not halt
c) the machine leaves the input unchanged
d) none of the above
CHOOSE YOUR ANSWERQ196. Consider the fa M given below
0 
1 

>*A 
A 
B 
B 
C 
B 
C 
A 
B 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ197. Consider the fa M given below
0 
1 

>*A 
A 
B 
B 
C 
B 
C 
A 
B 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ198. Consider the fa M given below
0 
1 

>*A 
A 
B 
B 
C 
B 
C 
A 
B 
The minimal finite automata accepting the same language as M has
a) 3 states b)4 states c) 5 states d) none of the above
CHOOSE YOUR ANSWERQ199. Consider the dfa given below
0 
1 

>A 
B 
C 
*B 
A 
C 
*C 
B 
A 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ200. Consider the dfa given below
0 
1 

>A 
B 
C 
*B 
A 
C 
*C 
B 
A 
Let S denote the set of all six bit binary strings in which the first and the fourth bits are 1 in the machine M obtained by interchanging the final and nonfinal states. The number of strings in S that are accepted by M is
(a) 1 (b) 4 (c) 7 (d) none of the above
CHOOSE YOUR ANSWERQ201. Consider the dfa given below
0 
1 

>A 
B 
C 
*B 
A 
C 
*C 
B 
A 
The minimal finite automata accepting the same language as M has
a) 3 states b)4 states c) 5 states d) none of the above
CHOOSE YOUR ANSWERQ202. The language accepted by a pushdown automata whose stack is limited to 10 items is best described as
A. Context free
B. Regular
C. Deterministic Context Free
D. Recursive
CHOOSE YOUR ANSWER[GATE 2001]
Q203. The language accepted by a deterministic pushdown automata whose stack is limited to 10 items is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ204. The language accepted by a two pushdown tape automata whose stacks are limited to 10^1000 items is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ205. The language accepted by a 1000 pushdown automata whose stacks are limited to 123456789 items is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ207. The language accepted by a pushdown automata whose input is limited to 10 items is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ209. The language accepted by a turing machine whose input tape is limited to 10 squares with a finite input and finite tape alphabet is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ210. The language accepted by a multitape, multiheaded, multitrack nondeterministic turing machine whose input tape is limited to 10 cells and whose input and tape alphabet is finite is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ211. The language accepted by a pushdown automata which never uses its stack is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ212. The language accepted by a turing machine whose ink dries up after printing 1000 symbols is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ213. The language accepted by a multiheaded, multitape, multidimensional, nondeterministic turing machine whose ink has dried up after 1,000,000 symbols printed is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ214. The language accepted by a linear bounded automata whose ink dries up after 100000000000 symbols printed is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ215. The language accepted by a deterministic linear bounded auotmata whose input tape is limited to 100000000000000000000000000000 cells is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recursive
CHOOSE YOUR ANSWERQ216. The language accepted by a finte automata with 100000000000000000 states as the upper limit is best described as
a. Context free
b. Regular
c. Deterministic Context Free
d. Recusive
CHOOSE YOUR ANSWERQ217. The C language is
a. A context free language
b. A context sensitive language
c. A regular language
d. Parsable fully only by Turing machines
CHOOSE YOUR ANSWER[GATE 2002]
Q218. The Java language is
a. A context free language
b. A context sensitive language
c. A regular language
d. Parsable fully only by Turing machines
CHOOSE YOUR ANSWERQ219. The C++ language is
a. A context free language
b. A context sensitive language
c. A regular language
d. Parsable fully only by Turing machines
CHOOSE YOUR ANSWERQ220. Machine language for the random access computer is
a. A context free language
b. A context sensitive language
c. A regular language
d. Parsable fully only by Turing machines
CHOOSE YOUR ANSWERQ221. Assembly language is
a. A context free language
b. A context sensitive language
c. A regular language
d. Parsable fully only by Turing machines
CHOOSE YOUR ANSWERQ222. To evaluate an expression without any embedded function calls
a. one stack is enough
b. two stacks are needed
c. as many stacks as the height of the expression tree are needed
d. a Turing machine is needed in the general case
CHOOSE YOUR ANSWER[GATE 2002]
Q223. The smallest finite automaton which accepts the language {x length of x is divisble by 3} has
a. 2 states
b. 3 states
c. 4 states
d. 5 states
CHOOSE YOUR ANSWER[GATE 2002]
Q224. The smallest finite automaton which accepts the language {x length of x is divisble by 30} has
a. 20 states
b. 30 states
c. 40 states
d. 50 states
CHOOSE YOUR ANSWERQ225. The smallest finite automaton which accepts the language {x length of x is divisble by 500} has
a. 200 states
b. 300 states
c. 400 states
d. 500 states
CHOOSE YOUR ANSWERQ226. Which of the following is true?
a. The complement of a recursive language is recursive
b. The complement of a recursively enumerable language is recursively enumerable
c. The complement of a recursive language is either recursive or recursively enumerable
d. The complement of a contextfree language is contextfree
CHOOSE YOUR ANSWER[GATE 2002]
Q227. Given that L is a recursively enumerable language which is not recursive and L1 is its complement which of the following statements about L1 is true?
a. L1 is necessarily recursive
b. L1 is necessarily recursively enumerable
c. L1 is either recursive or recursively enumerable
d. L1 is not recursively enumerable
CHOOSE YOUR ANSWERQ228. Consider the nfa below
a 
b 

>A 
A,B 
A 
B 
 
C 
C 
 
D 
*D 
 
 
Which of the following statements about the machine above is true?
a. the language accepted is (ab)*abb
b. the language accepted is (a+b)*
c. the language accepted is (a+b)+
d. the language accepted is (ab)*aab
CHOOSE YOUR ANSWER[GATE 2002 MODIFIED]
Q229. The minimal dfa for the language (ab)*abb has
a) 3 states b)4 states c)5 states d) none of the above
[GATE 2002 MODIFIED]
CHOOSE YOUR ANSWERQ230. Consider the dfa below
a 
B 

>Qs 
Qa 
Qs 
Qa 
Qa 
Qab 
Qab 
Qa 
Qabb 
*Qabb 
Qa 
Qs 
The minimal dfa for the above machine has
a) 3 states b)4 states c)5 states d) none of the above
CHOOSE YOUR ANSWER[GATE 2002 MODIFIED]
Q230. Let L be a language accepted by some turing machine and L1 its complement also accepted by a turing machine then choose the correct statement
a) L is recursively enumerable but not necessarily recursive
b) L is recursive but L1 is not necessarily recursive
c) Both L and L1 are recursively enumerable but not necessarily recursive
d) Both L and L1 are recursive
CHOOSE YOUR ANSWERQ231. Let L be a language accepted by some nondeterministic multitape turing machine and L1 its complement also accepted by a two pushdown tape machine then choose the correct statement
a) L is recursively enumerable but not necessarily recursive
b) L is recursive but L1 is not necessarily recursive
c) Both L and L1 are recursively enumerable but not necessarily recrsive
d) Both L and L1 are recursive
CHOOSE YOUR ANSWERQ232. Let L be a language accepted by some nondeterministic multitape turing machine and L1 its complement also accepted by a nondeterministic two pushdown tape machine then choose the correct statement
a) L is recursively enumerable but not necessarily recursive
b) L is recursive but L1 is not necessarily recursive
c) Both L and L1 are recursively enumerable but not necessarily recursive
d) Both L and L1 are recursive
CHOOSE YOUR ANSWERQ233. Choose the correct statement
a) there exists a universal turing machine which can simulate any turing machine M on its input w
b) there does not exist a universal turing machine which can simulate any turing machine on its input w
c) the set Ld={<Mi,wi> the encoding Mi of the ith turing machine does not accept the input wi, in an enumeration of turing machines and input strings} is recursively enumerable
d) the universal language is recursive
CHOOSE YOUR ANSWERQ234. The printing problem of turing machines is whether a turing machine ever prints a 1 on its tape. Ram takes the set L={<M,w> encoding of turing machine M that does not accept w} which is known to be undecidable. He modifies M such that in an accepting state no moves are made. Shyam further modifes M to M1 so that in an accepting state it prints a 1 and then halts. Choose the correct statement.
a) We can conclude that M1 prints a 1 and halts only if M accepts w, and thus the printing problem reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily recursively enumerable
d) None of the above.
CHOOSE YOUR ANSWERQ235. The state problem of turing machines is whether a turing machine ever enters a state q. Ram takes the set L={<M,w> encoding of turing machine M that does not accept w} which is known to be undecidable. He modifies M such that in an accepting state no moves are made. Shyam further modifes M to M1 so that in an accepting state it moves to state q and then halts. Choose the correct statement.
a) We can conclude that M1 halts only if M accepts w, and thus the state problem reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily recursively enumerable
d) None of the above.
CHOOSE YOUR ANSWERQ236. The printing problem of turing machines is whether a turing machine ever prints a 111 on its tape. Ram takes the set L={<M,w> encoding of turing machine M that does not accept w} which is known to be undecidable. He modifies M such that in an accepting state no moves are made. Shyam further modifes M to M1 so that in an accepting state it prints a 111 and then halts. Choose the correct statement.
a) We can conclude that M1 prints a 111 and halts only if M accepts w, and thus the printing problem reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily recursively enumerable
d) None of the above.
CHOOSE YOUR ANSWERQ237. The blank tape halting of turing machines is whether a turing machine started on blank tape halts. Ram takes the set L={<M,w> encoding of turing machine M that does not accept w} which is known to be undecidable. He modifies M such that in an accepting state no moves are made. Shyam further modifes M to M1 so that it starts with a blank tape and first prints w on the tape and behaves just like M. Choose the correct statement.
a) We can conclude that M1 halts only if M accepts w, and thus the printing problem reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily recursively enumerable
d) None of the above.
CHOOSE YOUR ANSWERQ238. The aim of the following questionis to prove that the language {M M is the code of a turing machine which, irrespective of the input, halts and outputs a 1, is undecidable. This is to be done by reducing from the language {M’,xM’ halts on x}, which is known to be undecidable.
Ram proceeds as follows. He takes the turing machine M and modifies it so that it makes no moves in its final state and then it prints a 1 in the final state and halts. Shyam further modifies this M so that it initially takes an arbitrary turing machine M’ and its input x, and if M’ accepts and halts on x then M will start its operation otherwise not. This he achieves by having M enumerate turing machines and strings till the encoding for M’ and x are obtained.
Choose the correct statement
a) the modified M will accept all strings and print a 1 provided M halts on w, but we have a decision problem for M’ then we can resolve whether M halts on w
b) M’ is always recursive and the modified M accepts a recursive language
c) The above argument shows that M’ is recursively enumerable
d) The above argument shows that M’ is recursive but not necessarily context sensitive
CHOOSE YOUR ANSWERQ239. The emptiness problem for r.e. sets is whether for any r.e. set L we can decide if L=j . As L is a subset of {a} we conclude that
a) L does not satisfy the containment property so L cannot be r.e.
b) L is a regular set as {a} is regular
c) L is recursive always
d) L is recursively enumerable
CHOOSE YOUR ANSWERQ240. The completeness problem for r.e. sets is whether for any r.e. set L we can decide if L=S *.
a) as no finite subset of L can be the same as L we conclude that the set L is not r.e.
b) L is r.e. as L is regular
c) L is recursively enumerable as we only require a turing machine that halts on all inputs
d) L is recursive but not necessarily contextfree
CHOOSE YOUR ANSWERQ241. The regularity problem for r.e. sets is whether for any r.e. set L, is L regular?
a) the regularity problem is decidable
b) as the regular sets are contained in the contextfree languages if the regularity problem is decidable then by the containment property every cfl must be regular
c) every r.e. set is trivially seen to be regular as every turing machine has a finite control
d) as every regular set is contained in the set of all strings, the latter must be in L by the containment property and that is known to be undecidable.
CHOOSE YOUR ANSWERQ242. The contextfreeness problem for r.e. sets is whether for any r.e. set L, is L contextfree?
a) the contextfreeness problem is decidable
b) as the regular sets are contained in the contextfree languages if the regularity problem is decidable then by the containment property every cfl must be regular
c) every r.e. set is trivially seen to be contextfree as every turing machine has a finite control
d) as every contextfree language is contained in the set of all strings, the latter must be in L by the containment property and that is known to be undecidable.
CHOOSE YOUR ANSWERQ243. The recusiveness problem for r.e. sets is whether for any r.e. set L, is L recursiver?
a) the recusiveness problem is decidable
b) as the regular sets are contained in the recursisve if the regularity problem is decidable then by the containment property every recursive set must be r.e.
c) every recursive set is trivially seen to be regular as every turing machine has a finite control
d) as every recursive set is contained in the set of all strings, the latter must be in L by the containment property and that is known to be undecidable.
CHOOSE YOUR ANSWERQ244. Let L0={<M,0>M is the encoding of a turing machine that accepts the empty set}
And L1={<M,1>M is the encoding of a turing machine that does not accept the empty set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ245. Let L0={<M,0>M is the encoding of a turing machine that accepts an infinite ty set}
And L1={<M,1>M is the encoding of a turing machine that does not accept an infinite set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ246. Let L0={<M,0>M is the encoding of a turing machine that accepts a singleton set}
And L1={<M,1>M is the encoding of a turing machine that does not accept a singleton set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ247. Let L0={<M,M’,0>M,M’ are the encodings of turing machines that accept the empty set}
And L1={<M,M’,1>M,M’ are the encodings of a turing machines that either one or both do not accept the empty set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ248. Let L0={<M,0>M is the encoding of a turing machine that accepts a cfl}
And L1={<M,1>M is the encoding of a turing machine that does not accept a cfl}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ249. Let L0={<G,G’,0>G,G’ are the encodings of cfgs that generate the same set}
And L1={<G,G’,1>G,G’ are the encodings of cfgs that either one or both do not generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ250. Let L0={<G,G’,0>G,G’ are the encodings of regular grammars that generate the same set}
And L1={<G,G’,1>G,G’ are the encodings of regular grammars that either one or both do not generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ251. Let L0={<G,G’,0>G,G’ are the encodings of cfgs that generate infinte languages}
And L1={<G,G’,1>G,G’ are the encodings of cfgs that either one or both do not generate infinite sets}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ253. Let L0={<G,G’,0>G,G’ are the encodings of csgs that generate the same set}
And L1={<G,G’,1>G,G’ are the encodings of csgs that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ254. Let L0={<G,G’,0>G,G’ are the encodings of unrestricted grammars that generate the same set}
And L1={<G,G’,1>G,G’ are the encodings of unrestricted grammars that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ255. Let L0={<G,G’,0>G,G’ are the encodings of linear bounded automata that generate the same set}
And L1={<G,G’,1>G,G’ are the encodings of linear bounded automata that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ256. Let L0={<G,G’,0>G,G’ are the encodings of unrestricted grammars such that they generate L and LR respectively with L=LR}
And L1={<G,G’,1>G,G’ are the encodings of unrestricted grammars that generate languages L and LR with L not the same as LR respectively}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ257. Let L0={<G,G’,0>G,G’ are the encodings of C programs that produce the same output for all inputs}
And L1={<G,G’,1>G,G’ are the encodings of C programs that do not produce the same output for all inputs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ259. Let L0={<G,G’,0>G,G’ are the encodings of C programs that produce some output for all inputs}
And L1={<G,G’,1>G,G’ are the encodings of C programs that do not produce some output for all inputs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ260. Let L0={<G,G’,0>G,G’ are the encodings of C programs that loop on some input}
And L1={<G,G’,1>G,G’ are the encodings of C programs that do not loop on some input}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ261. Let L0={<G,G’,0>G,G’ are the encodings of cfgs where the intersection of the langugaes generated is a cfl}
And L1={<G,G’,1>G,G’ are the encodings of cfgs where the intersection of the languages generated is not a cfl}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ262. Let L0={<G,G’,0>G,G’ are the encodings of cfgs that generate regular sets}
And L1={<G,G’,1>G,G’ are the encodings of cfs that both or either does not generate a regular set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ263. Let L0={<G,G’,0>G,G’ are the encodings of cfgs such that L(G’) is contained in L(G)}
And L1={<G,G’,1>G,G’ are the encodings of cfgs sucht that L(G’) is not contained in L(G)}. Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ264. Let L0={<G,G’,0>G,G’ are the encodings of cfgs which generate languages whose complement is also a cfl}
And L1={<G,G’,1>G,G’ are the encodings of C programs that generate languages whose complement is not both a cfl}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ265. Let L0={<G,G’,0>G,G’ are the encodings of ambiguous cfgs}
And L1={<G,G’,1>G,G’ are the encodings of unambiguous cfgs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ266. Let L0={<G,G’,0>G,G’ are the encodings of inherently ambiguous cflss}
And L1={<G,G’,1>G,G’ are the encodings of cfls that are not inherently ambiguous}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L’ is recursive
b) L is recursive and L’ is recursively enumerable
c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable
CHOOSE YOUR ANSWERQ267. Choose the false statement
a) PCP over a one symbol alphabet is decidable
b) It is undecidable if a csl is a cfl
c) It is undecidable if a turing machine accepts at least 10 inputs
d) It is undecidable if two regular grammars generate the same set
CHOOSE YOUR ANSWER