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 *
Q2. Consider the set of all strings S * over an alphabet S ={a,b} with the
concatenation operator for strings, and
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
Q3. Consider the set of all strings S * over the alphabet S ={a,b,c,d,e} with
the concatenation operator for strings.
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
Q4. 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
Q5. Consider the language defined as follows
L= {a^n b^n|n>=1} if P=NP
And
L={ww|w 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
Q6. 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
Q7. 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
Q8. 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
a. L is a context-free 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
Q9. 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
a. The type of L is undecidable because of the halting problem
b. L is a context-sensitive language
c. L is recursively enumerable and not context-free
d. L is context sensitive and not regular
Q10. Consider the language L defined below
L=(0+1)* if P=NP
And
L=(a^nb^n|n>=1} otherwise
a. Whether L is a regular set that is not context-free will be known after we
resolve the P=NP question.
b. Whether L is context-free but not regular will be known after we resolve the
P=NP question
c. L is context-sensitive
d. L is not recursive
Q11. 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^n|n>=234} if L1=L2
And
L={a^nb^nc^nd^n|n>=678} otherwise
a. L is recursive
b. L is context-free
c. We can never say anything about L as it is undecidable
d. L is regular
Q12. 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^n|n>=34567} otherwise
a) L is recursive
b) L is context-free and not context-sensitive
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
Q14. 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 3-sat is in P
L=(0*1*)* if 3-sat 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 max-clique problem is in P
L=(0*(00)*(1*11*)*) * if node-cover problem is not in P
L=(0*1*)****(010)* if edge-cover 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
Q15. 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 n-1 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 context-sensitive but not regular
c) L is context-free but not regular
d) L is not a finite set
Q16. We are given two context-free 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
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 context-sensitive
d) L is context-sensitive but not context-free
e) L is context-free but not regular
Q17. 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 iscontext-free
c) L is context-sensitive
d) The above choices can be resolved only if we know if L(G) is inherently
ambiguous or not
Q18. 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
Q19. 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
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
Q20. 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
