# 6. Control questions and tasks / Контрольні запитання і завдання

## Finite state machines

1. Define a **finite state machine**: its states, alphabet, transition function,
   start state, and accepting states.
2. What does it mean for a machine to **emit** output during a transition? How
   does that turn a recogniser into a scanner (transducer)?
3. Why is it useful to group input characters into **classes** (`DIGIT`, `DOT`,
   `MINUS`, `OTHER`) before writing the transition table?

## The number scanner

4. What is the role of the **emitting** states `INT` and `FRAC`? When exactly is
   a number **emitted**?
5. In the scanner, how is the character `-` treated differently when finding
   **positive** rationals versus **signed** rationals?
6. Why does the isolated dot in `...fn.f143...` produce **no** number? What
   condition must hold before a `DOT` extends a number?
7. Why must a **sentinel** (end-of-input) be handled so that the last number is
   not lost?

## Reasoning and complexity

8. What is the time complexity of the scanner in terms of the input length $n$?
   How much memory (besides the output) does it use?
9. Draw (or tabulate) the transition diagram of the **integer** scanner — the
   two-state machine that collects maximal runs of digits.

## Tasks by hand

10. Trace the **integer** scanner on the string `a12b3` and list the tokens it
    emits, showing the state after each character.
11. Give the output of each of the four scanners on the input `x-5.6y7`.
12. Modify the transition table so that the scanner also accepts a number with a
    leading `+` sign (e.g. `+42`). Which state and transitions change?