1) Construct a Markov Algorithm that will reverse the order of an input string that consists of zero or more upper case letters. ABCDE should become EDCBA, AB should become BA, A should stay A, and A should stay A. NOTE: Your algorithm must handle strings of ANY length, not just length 0-5. Demonstrate that your algorithm works by constructing a table similar to Table 1.11 on page 37 of the text for each of the input strings A, A, AB, ABC and ABCD (a separate table for each input).
To reduce the size of these tables, show only the lines where the rule succeeds. For example, using this approach, Table 1.11 would become simply
Rule Success or Failure String
3 S αABC
1 S BαAC
1 S BCαA
2 S BCA
2) If A appears on the LHS of a rule, it only makes sense for it to appear alone. It also only makes sense for that rule to be your last rule, because it will always be satisfied. It will always have the following effect: whatever is on the RHS of that rule (except the period, if there is one) will be put at the beginning of your working string.
3) If A appears on the RHS of a rule, it only makes sense for it to appear alone (except that it may be followed by a period). The substring of your working string that matches the LHS of this rule will be deleted when this rule executes.
4) The original input string will always consist of a string of zero or more upper case letters (A-Z). It is possible for the input string to be empty (A).
5) Your rules can introduce new characters that can appear temporarily in the working strings. These characters will be lower case Greek symbols like, a, 13, y, etc. In general, it makes sense for these symbols to not appear in the final result, but while they are there, they should be treated just like the upper case letters in that they can satisfy a match for a variable just as well as an upper case letter. For example, if the rule being looked at is xy -> yx and the current string is aAB, then the rule would change the string to AaB.
6) The lower case letters (a-z) are variables that match exactly one symbol (they do not match A). As I said above, they can match an upper case letter or a lower case Greek letter.
7) An upper case letter or lower case Greek letter on the LHS of a rule is like a constant and must be matched exactly in the working string (upper case letters don't often appear in rules, however).
8) Every time a rule actually executes, you start by considering the rules from the top again and you start by looking at the beginning of the current string.
Execution stops either when a rule that ends with a period is executed or if the working string does not cause any of the rules to fire.
In one last attempt to clarify questions before they occur, here is a table that shows a few examples (please note that each example is independent of the others):
Rule Being Considered Current String Match? String Afterwards
axY -> Yax ABC No ABC
cocY -> Yax CaAB Yes CBaA
axY -> Yax aA13 Yes (3aA (please note!)
coW -> Yax BaA No BaA
xy -> A ABC Yes C (and quits)
xy -> A. AaB Yes B (and quits)
xy -> A. B No B
A ->13 ABC Yes ABC
A -> p ABC Yes P13ABC
A -> p A Yes 13