Theory Of Computation Test – Question 11

Let A be any language over .We say that strings x and y in  are indistinguishable by A iff for every string z   either both xz and yz are in A or both xz and yz are not in A. We write x A y in this case. Notice that the relation A on is an Equivalence relation.

Suppose that ={a,b} and L={anbn | n0}, Now consider the following statements.

  1. Set L is a subset of one of the equivalence class of relation L
  2. Let S= {ai |i>=0}, then No Two elements of S belongs to same equivalence class of L.

Which of the above statements is/are True?

  • 1.
  • 2.
  • 3.
  • 4.

Leave a Reply

Your email address will not be published. Required fields are marked *