Reference no: EM131213513

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