CDM/Laboratory/Laboratory8/6questions
Raw

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

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

Reasoning and complexity

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

Tasks by hand

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

Laboratory/Laboratory8/6questions.md · 1.6 KB · updated 2026-08-01 20:19