b. Let Σ be an alphabet. Let x = a₁a2a3... an, n ≥ 1, be an arbitrary string in E+. Let L = {x}. In each of the followin

[answerhappygod]

1 (155.24 KiB) Viewed 37 times

b. Let Σ be an alphabet. Let x = a₁a2a3... an, n ≥ 1, be an arbitrary string in E+. Let L = {x}. In each of the following you are given two possible answers, labelled indistinguishable and dis- tinguishable, respectively. Circle either one of the labels, then complete the sentence following the label you have circled. (i) Let ₁ and 2 be two prefixes of x, x₁ # 12. Let and 2. distinguishable: For z = (If i = 0, we take x₁ = A.) Then ₁ and 2 are 1. indistinguishable: For all z € *, ₁z. 2. distinguishable: For z =_ x1z (iii) Let x₁ = a₁a2... ai, i ≥ 0 Land x₂z. I1Z (ii) Let x1, x2 € Σ*, 1 # x2, be two strings that are not prefixes of x. Then ₁ and 2 are 1. indistinguishable: For all z € Σ*, £12- x2 = a₁a2...aj, j>i. 2. distinguishable: For z = I12. Therefore, there are in total. They are L and 22 Land 22. I1 = a₁a2... ai, i ≥ 0 be a prefix of x, and 22 € * a string that is not a prefix of x. Then 21 and 22 are 1. indistinguishable: For all z € Σ*, €17. Land 22. L and 22. Land 22 L. L. L. L. L. L. equivalence classes with respect to Ic.