![Given an arbitrary alphabet Σ ={a,a2, ,an), we can impose a total ordering on it in the sense that we can define < so that ai < a2 < an. We now proceed to define a new operation called the SORT of a string w = wjw2 wk E Σ* (where wi E Σ and k = IwD as: SORT(w) = wo(1)w0(2)..Ma(k) so that wW (i) < w σ(i+1) for i is k-1 and σ is a permutation (i.e., a 1-to-1 onto mapping : [ 1 ..k]→[ 1 ..kD For example, SORT(11 21 001 01 20)=00001 1 1 1 1 22. Now extend the definition of SORT to languages, so that SORT( L)-(SORT(w) | we L). For each one of the following statements, state whether it is true or false and explain:](https://d2vlcm61l7u1fs.cloudfront.net/media%2Fc97%2Fc976f2b2-ca78-4b46-a556-6373cbc6a3e9%2FphpnVNFOn.png)
Given an arbitrary alphabet Σ ={a,a2, ,an), we can impose a total ordering on it in the sense that we can define
Answered Essay: Given an arbitrary alphabet Σ ={a,a2, ,an), we can impose a total ordering on it in the sense that we can define
Expert Answer
We know that is the set of all words formed by by alphabets in
.
a)
For a operation to be regular on a set, the set must be closed under that operation.
Let . Clearly,
as
is just a permutation of
. This means,
is closed under operation
. Thus,
is regular.
b)
Let, . Now,
. Thus,
c)
Let . From definition of sort we have,
.
Clearly
g)
No, doesn’t always preserve regularity. This is because for a operation to be regular on a set, the set must be closed under that operation. However
doesn’t always follow this property. For example –
Let, . Now,
. Thus,
doesn’t preserve regularity.
h)
Decidable languages are the decision problems which are algorithmically solvable. Since, is an operation for which many well-known algorithms are present (Bubble Sort, Insertion Sort etc) , we can say that
preseves decidability.
i)
Undecidable languages are the decision problems which are not algorithmically solvable. Since, is an operation for which many well-known algorithms are present (Bubble Sort, Insertion Sort etc) , we can say that
doesn’t preseve non-decidability.
