2. Methodical guidelines / Методичні вказівки #

This section is self-contained: it develops the theory of the work’s theme — finite state machines and their use for scanning numbers — together with algorithms for the tasks in 4task.md. No outside material is required.

2.1 Finite state machines #

A finite state machine (FSM) consists of a finite set of states, an input alphabet, a start state, a set of accepting states, and a transition function that, given the current state and the next input symbol, gives the next state. The machine reads the input once, left to right, holding only its current state as memory. For scanning we also let a transition emit an output (a recognised token) — a machine with output is a transducer.

2.2 Character classes #

The exact character does not matter, only its class. For numbers we need four:

Classifying first keeps the transition table small.

2.3 Four scanners of increasing power #

The tasks build one machine in stages. Each stage adds states:

1. Digits — no grouping at all: whenever the current character is a DIGIT, output that digit. The result is every digit of the string, concatenated.
2. Integers — group maximal runs of digits: stay in an “in-number” state while reading digits, and emit the collected run when a non-digit arrives.
3. Positive rationals — allow one decimal point inside a number: after the integer part, a DOT followed by more digits extends the same number (143.31); a MINUS is treated as a separator, so numbers stay positive.
4. Signed rationals — allow an optional leading MINUS: a - immediately before a number’s digits becomes part of it (-113.112).

2.4 Transition table for the signed-rational scanner #

States: START (between numbers), SIGN (a - that may begin a number), INT (reading the integer part), FRAC (reading digits after the dot). The states INT and FRAC are the emitting states (a transducer has no accepting states): reaching a non-number character — or the end of input — while in one of them emits the number built so far.

Restricting this machine gives the earlier tasks: drop the SIGN state (treat MINUS as OTHER) for positive rationals; also drop FRAC (treat DOT as OTHER) for integers.

2.5 The scanner in pseudocode #

function scanNumbers(s, allowSign, allowFraction):
    tokens ← empty list
    buffer ← ""            # characters of the number under construction
    state  ← START
    append a sentinel OTHER character to s   # forces a final emit

    for each character c in s:
        cls ← class of c                     # DIGIT, DOT, MINUS, OTHER

        if state == START or state == SIGN:
            if cls == DIGIT:            buffer ← buffer + c;  state ← INT
            else if cls == MINUS and allowSign and state == START:
                                        buffer ← "-";         state ← SIGN
            else:                       buffer ← "";          state ← START

        else if state == INT:
            if cls == DIGIT:            buffer ← buffer + c
            else if cls == DOT and allowFraction:
                                        buffer ← buffer + ".";  state ← FRAC
            else:                       emit(buffer, tokens);   buffer ← ""
                                        handle c as in START     # sign/other

        else if state == FRAC:
            if cls == DIGIT:            buffer ← buffer + c
            else:                       emit(buffer, tokens);   buffer ← ""
                                        handle c as in START

    return tokens

emit converts the buffered text to a number and appends it. The three variants are scanNumbers(s, false, false) (integers), scanNumbers(s, false, true) (positive rationals), and scanNumbers(s, true, true) (signed rationals); the digit task needs no buffer at all — just output each DIGIT.

2.6 Worked example #

On adfvq3414fn.f143.31f-113.112vwe the machine yields, at each stage:

• digits: 341414331113112
• integers: [3414, 143, 31, 113, 112]
• positive rationals: [3414, 143.31, 113.112] (the - is a separator)
• signed rationals: [3414, 143.31, -113.112] (the - joins the number)

Note the isolated dot in fn.f produces no number (no digit precedes it), and the same - is either a separator or a sign depending on the machine.

2.7 Complexity #

The scanner reads each character once and does constant work per character, so it runs in $O(n)$ time for an input of length $n$, using $O(1)$ state plus the space for the emitted tokens. This linear, single-pass behaviour is the defining strength of finite state machines.

Laboratory/Laboratory8/2method.md · 5.5 KB · updated 2026-08-01 18:44