# Theory Of Computation Test – Question 11

Let A be any language over ${\sum}&space;^*$.We say that strings x and y in ${\sum}&space;^*$ are indistinguishable by A iff for every string z $\epsilon$ ${\sum}&space;^*$ either both xz and yz are in A or both xz and yz are not in A. We write x $\equiv$A y in this case. Notice that the relation $\equiv$ A on ${\sum}&space;^*$is an Equivalence relation.

Suppose that ${\sum}&space;^*$={a,b} and L={anbn | n$\geqslant$0}, Now consider the following statements.

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

Which of the above statements is/are True?

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

About Admin