The Finite State Text-Processing Machine

A finite state machine (FSM) is essentially a directed graph. Each node of the graph is a state; at any moment during the FSM's execution one of the states is the current state. Each directed edge between two states is a transition. When the conditions are right, one transition leaving the current state occurs and the current state changes to the new state that the transition points to.

Consider the following very simple example.

This FSM has two states, labeled A and B, and three transitions, labeled 1, 2, and 3. If the current state is A and the conditions for transition 1 are met, the current state becomes B. When the current state is B and the conditions for transition 2 are met, the current state becomes A again. If the current state is B and the conditions for transition 3 are met, the current state stays B.

In this problem the input describes several FSMs. Each transition has an associated set of characters called its input set and a string called its output string. A transition may occur when the current input character is in the transition's input set. When the transition occurs, its output string is printed.

The input is a sequence of pairs {FSM description, input for the FSM}. An FSM is described by the following items, separated by whitespace (spaces, tabs, and end-of-line characters):

• An integer giving the number of states. For each state, in order:
  • A 1-to-8 character state name. Names are case sensitive and unique.
  • An integer giving the number of transitions that leave this state. For each transition, in order:
    • the input set of characters that enable the transition;
    • the name of the new current state when the transition occurs;
    • the output string.

Input sets and output strings are sequences of printable characters with no embedded whitespace. The following escape constructions may appear:

• \b — a blank (space).
• \n — an end-of-line.
• \\ — a single backslash.
• \0 — appears only in an output string; print nothing when the transition occurs.
• \c — as an input set it matches any character: if none of the current state's other transitions are enabled, the transition whose input set is \c is enabled. As an output string it prints the current input character (it may appear several times in one output string).

After an FSM description has been fully read, the machine begins executing on the characters that start on the first complete line following the description. The starting state is always named START, and the final state is always named END (END never appears as a state in the description). Characters are fed one at a time — across line boundaries if necessary — until the machine reaches END. The end-of-line character is matched only by an input set of \n; if the current state has no \n transition, the end-of-line is consumed with no output and the state is left unchanged. A state count of 0 ends the input. All input is guaranteed to be correct.

For the k-th FSM (k = 1, 2, …) print a line containing exactly

Finite State Machine k:

and then, beginning on the next line, the output produced by that machine's transitions.

The provided examples illustrate this. The first FSM replaces every vowel on a single line with an asterisk. The second deletes every vowel that follows an upper- or lower-case X, again processing a single line. The third toggles the case of every odd-numbered vowel; processing stops when an exclamation point is reached, and the remainder of that input line is ignored.