# Question: In order to transform one source string of text x 1 m

In order to transform one source string of text x [1 ¬ m] to a target string y [1 ¬ n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to y. We use an array z—assumed to be large enough to hold all the characters it will need—to hold the intermediate results. Initially, z is empty, and at termination, we should have z[j] = y[j] for j = 1, 2, ..., n. We maintain current indices i into x and j into z, and the operations are allowed to alter z and these indices. Initially, i = j = 1. We are required to examine every character in x during the transformation, which means that at the end of the sequence of transformation operations, we must have i = m + 1. There are six transformation operations:

• Copy a character from x to z by setting z[j] ← x[i] and then incrementing both i and j. This operation examines x[i].

• Replace a character from x by another character c, by setting z[j] ← c, and then incrementing both i and j. This operation examines x[i].

• Delete a character from x by incrementing i but leaving j alone. This operation examines x[i].

• Insert the character c into z by setting z[j] ← c and then incrementing j, but leaving i alone. This operation examines no characters of x.

• Twiddle (i.e., exchange) the next two characters by copying them from x to z but in the opposite order; we do so by setting z[j] ← x[i + 1] and z[j + 1] ← x[i] and then setting i ← i + 2 and j ← j + 2. This operation examines x[i] and x [i + 1].

• Kill the remainder of x by setting i ← m + 1. This operation examines all characters in x that have not yet been examined. If this operation is performed, it must be the final operation.

• Copy a character from x to z by setting z[j] ← x[i] and then incrementing both i and j. This operation examines x[i].

• Replace a character from x by another character c, by setting z[j] ← c, and then incrementing both i and j. This operation examines x[i].

• Delete a character from x by incrementing i but leaving j alone. This operation examines x[i].

• Insert the character c into z by setting z[j] ← c and then incrementing j, but leaving i alone. This operation examines no characters of x.

• Twiddle (i.e., exchange) the next two characters by copying them from x to z but in the opposite order; we do so by setting z[j] ← x[i + 1] and z[j + 1] ← x[i] and then setting i ← i + 2 and j ← j + 2. This operation examines x[i] and x [i + 1].

• Kill the remainder of x by setting i ← m + 1. This operation examines all characters in x that have not yet been examined. If this operation is performed, it must be the final operation.

**View Solution:**## Answer to relevant Questions

Suppose that you are given an n × n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step you may move the checker ...Show that if (S, ℓ) is a matroid, then (S, ℓ′) is a matroid, where ℓ′ = {A′: S - A′ contains some maximal A ¬ℓ}. That is, the maximal independent sets of (S, ...Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Show how to implement a counter as an array of bits so that any sequence of n INCREMENT and RESET operations takes ...The PERT chart formulation given above is somewhat unnatural. It would be more natural for vertices to represent jobs and edges to represent sequencing constraints; that is, edge (u, v) would indicate that job u must be ...Give a type definition for a scalar type called CIRCLE, what selectors and The-operators apply to this type? Also:a. Define a set of read only operators to compute the diameter, circumference, and area of a given circle.b. ...Post your question