Question

Lab 2

∑={0,1} L = {w : if |w| is odd w begins with 11}.

List the indistinguishability classes for L(M). Include the following information for each class c, where w_c is a string in c:

• A short description or characteristic function that describes the strings in c.

• Whether w_c is or is not in L(M).

• ∀z(w_cz ∈ L(M) iff … ). This rule must be different for each equivalence class — that is what makes them different classes.

• The class transitions for each symbol in Σ: w_ca ∈ [n_a] and Σ: w_cb ∈ [n_b], where n_a and n_b are the numbers of equivalence classes.

Answer 1

Let's say the give function is L(language)= { W : if |W| is odd and begins with 11} and Alphabet is = {0,1}

The language is the set of strings which are in "ODD" length and starts with "11" string so the the strings in language can be like odd length start with "11"

Strings in "C" can be a set of all odd length strings that contain exactly two 1s by starting of the strings

Strings in 'c' are {110,111,11000,11011, .....}    =    W_c

let say x = alphabet "0" and Y = alphabet "1"

                               Y

                      epsilon      1           11         111         1111        11111

     epsilon         Notinc Notinc    Notinc     InC       Notinc        InC

          0            Notinc Notinc    Notinc     NotInC    Inc            NotInC                Here The Strings are starting with Y only

         00           Notinc Notinc    Notinc       Inc       Notinc        Inc

X      000         Notinc Notinc      Inc         Notinc     Inc           Notinc

       0000         Notinc Notinc      Inc         Inc         Notinc        Inc

       00000      Notinc Notinc       Inc         Notinc       Inc         Notinc

form this W_c in L is like {111,11111,11110,11100,1110000,1100000,11110,1111000,1111000000,.....}

W_c Not in L is like {epsilon,1,0,00,000,11,1100,1110....}

Let's say N_a class function will be the { W : if |W| is odd and begins with 11}

And N_b class function will be the {Z(W_cZL(M) if and only if ends with "00"} which consists of Strings which are not in L are W_c which ends with 00.

Equivalence Definition:

Given a set L(Language) and an equivalence relations R, the equivalence classes of L are disjoint subsetsL1, L2, . . .of "L" whose union is "L"

such that if x , y ∈ Li then x R y where R is a relation ,but if x and y are in different subsets of Li And Lj for i and j are not equal Then it is not a Equivalence

List all the elements of the set L(Language ), say,x1, x2, x3, . . .. And Let's Assume the Relation is like

{Y | Y is the String which consists of odd number of 1's in the string}

If some Xi is not equivalent to any element seen so far then Xi starts a new equivalence class.

If some Xj is equivalent to some Xi seen earlier, then Xj is in the same equivalence class as Xi.

The number of equivalence classes is just the number of sets found this way in the limit.

If L is regular, then one can test if x equivalence to y by this way

Let M be a minimal deterministic finite automaton recognizing L

Then X equivalence of L to Y if and only if X and y both drive M from the start state to the same state of M

So the Equivalence class are the sub-sets of the language of class N_a and N_b And the Subsets are

N_a = {111,11111,11110,11100,1110000,1100000,11110,1111000,1111000000,.....}

N_b = {epsilon,1,0,00,000,11,1100,1110,1111000,1110000....}

The class transitions for each symbol in :W_ca belongsto [N_a] and :W_ca belongsto [N_b] where n_a and n_b are the number of equivalence classes

subsets are X1 = {1110000} X2 = {11100}   X3 = {1110000} by the relation of odd number of 1's in a string

Here X1 and X2 set of strings can be start and same state in the minimal deterministic finite automata so these X1 and X2 are Equivalence class by the taken relation

The Equivalence class are 2