[Problem F | 1993 Regional problem set | My ACM problem archive | my home page]

The Finite State Text-Processing Machine

There are two states in this FSM, 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, then the current state becomes B. When the current state is B, and the conditions for transition 2 are met, the current states becomes A again. If the current state is B and the conditions for transition 3 are met, the current state remains B.

In this problem the input will be descriptions of several FSMs. Each transition in these FSMs has an associated set of characters called the input set, and a string called the output string. A transition can occur when the current input data character is in the transition's input set. When the transition occurs, the output string is printed.

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

- An integer specifying the number of states in the FSM. for each
of these states there will be the following items, in order:
- A one to eight character name for the state. State names are case significant, and unique
- An integer specifying the number of transitions that leave the
current state. For each of these transitions there will be the
following data items, in order:
- The set of input characters that enable the transition (see below). the name of the new current state when this transition occurs
- The output string (see below).

After the last item in the description of and FSM has been read begin “executing” the FSM using the characters that start on the first complete line following the description. the beginning state will always be called START. The final state will always e called END, but will not appear as a state in the description of a FSM. All input is guaranteed to be correct.

The first example FSM replaces each vowel in a single line of input with an asterisk. The second example will delete each vowel that follows a lower or upper case X, again processing only a single line of input. The final example changes the case of each odd-numbered vowel in the input; processing stops when an exclamation point is encountered, and the remainder of the input line is ignored.

Sample Input

1 START 3 AEIOUaeiou START * \n END \n \c START \c This is input for example one. 2 START 3 \c START \c Xx SKIP \c \n END \n SKIP 4 AEIOU START \0 aeiou START \0 Xx SKIP \c \n END \n XaXxe Test XIo iXixO 3 START 12 \c START \c ! FINIS \0 A TWO a E TWO e I TWO i O TWO o U TWO u a TWO A e TWO E i TWO I o TWO O u TWO U TWO 4 \c TWO \c AEIOU START \c aeiou START \c ! FINIS \0 FINIS 2 \c FINIS \0 \n END \n This is some data for FSM number 3. ! IGNORED 0

Finite State Machine 1: Th*s *s *np*t f*r *x*mpl* *n*. Finite State Machine 2: XXx Test Xo iXx Finite State Machine 3: ThIs is sOme dAta fOr FSM numbEr 3.

1 START 2 \n END This_is_the_output_from_the_first_FSM.\n \c START \0 If this appears, the program failed for the first fsm. 1 START 2 \n END Testing\bfor\bproper\bhandling\bof\b\\b\band\b\\\\.\n \c START \0 If this appears, the program failed for the second fsm. 1 START 2 \n END \n \c START \c The third FSM is correct (it handles \c correctly). 1 START 3 AEIOUaeiou START * \n END \n \c START \c This is an example from the problem statement, with different text. 2 START 3 \c START \c Xx SKIP \c \n END \n SKIP 4 AEIOU START \0 aeiou START \0 Xx SKIP \c \n END \n XaXxe Test XIo iXixO (This is also from the problem statement). 3 START 12 \c START \c ! FINIS \0 A TWO a E TWO e I TWO i O TWO o U TWO u a TWO A e TWO E i TWO I o TWO O u TWO U TWO 4 \c TWO \c AEIOU START \c aeiou START \c ! FINIS \0 FINIS 2 \c FINIS \0 \n END \n This is some data for the FSM. There will be two lines of output. The last word on this line is FINIS.! IGNORED. 22 AA 2 \n FAIL \0 \c AB T AB 2 \n FAIL \0 \c AC h AC 2 \n FAIL \0 \c AD i AD 2 \n FAIL \0 \c AE s AE 2 \n FAIL \0 \c AF \b AF 2 \n FAIL \0 \c AG F AG 2 \n FAIL \0 \c AH S AH 2 \n FAIL \0 \c AI M AI 2 \n FAIL \0 \c AJ \b AJ 2 \n FAIL \0 \c AK d AK 2 \n FAIL \0 \c AL o AL 2 \n FAIL \0 \c AM e AM 2 \n FAIL \0 \c AN s AN 2 \n FAIL \0 \c AO \b AO 2 \n FAIL \0 \c AP w AP 2 \n FAIL \0 \c AQ o AQ 2 \n FAIL \0 \c AR r AR 2 \n FAIL \0 \c AS k AS 2 \n FAIL \0 \c AT . AT 2 \n END \n \c FAIL \0 FAIL 1 \c END THIS\bPROGRAM\bFAILED! START 1 \c AA \0 FAILURE FAILURE BAD! 0

Finite State Machine 1: This_is_the_output_from_the_first_FSM. Finite State Machine 2: Testing for proper handling of \b and \\. Finite State Machine 3: The third FSM is correct (it handles \c correctly). Finite State Machine 4: Th*s *s *n *x*mpl* fr*m th* pr*bl*m st*t*m*nt, w*th d*ff*r*nt t*xt. Finite State Machine 5: XXx Test Xo iXx (This is also from the problem statement). Finite State Machine 6: ThIs is sOme dAta fOr the FSM. ThEre wIll be twO linEs of OutpUt. The lAst word On this lIne Is FINiS. Finite State Machine 7: This FSM does work.

This page maintained by Ed Karrels.

Last updated September 20, 1999