# 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](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*.

![Turnstile finite state machine whose response to push or coin depends on its current Locked or Unlocked state](img/state_idea.png)

## 2.2 Character classes

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

| Class | Characters |
|---|---|
| `DIGIT` | `0`–`9` |
| `DOT` | `.` |
| `MINUS` | `-` |
| `OTHER` | anything else |

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.

![Transducers that produce output: a Moore machine emits in each state, a Mealy machine emits on each transition](img/moore_mealy.png)

| State | `DIGIT` | `DOT` | `MINUS` | `OTHER` |
|---|---|---|---|---|
| `START` | append → `INT` | `START` | start `-` → `SIGN` | `START` |
| `SIGN` | append → `INT` | drop → `START` | drop → `START` | drop → `START` |
| `INT` | append → `INT` | append → `FRAC` | **emit**, start `-` → `SIGN` | **emit** → `START` |
| `FRAC` | append → `FRAC` | **emit** → `START` | **emit**, start `-` → `SIGN` | **emit** → `START` |

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

```text
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.