CDM/Laboratory/Laboratory8/main
Raw

Laboratory Work 8 — Finite State Machines: Scanning Numbers in a String

Eighth laboratory work of Computer Discrete Mathematics. You design a finite state machine that scans a string character by character and extracts numbers from it — progressively: bare digits, then integers, then positive rationals, then signed rationals.

At a glance

Topic Finite state machines: scanning a string to extract digits, integers, and rational numbers
Prerequisite lectures L14 — Automata theory
Deliverable Source code + report (see 5report.md)
Grading Banded, four tasks of increasing difficulty (see 4task.md)

Contents

# Part File
1 Objective 1purpose.md
2 Methodical guidelines (theory & algorithms) 2method.md
4 Task and order of execution 4task.md
5 Report contents 5report.md
6 Control questions 6questions.md

Conventions

  • Language — source code and the report are in English.
  • Implement it yourself — no built-in shortcuts. Do not call a library or built-in that performs the core task for you (e.g. no HashSet/set()/Set for sets, no library graph/relation type, no math.gcd, no eval). Build the mechanism from basic primitives — arrays/lists, loops, arithmetic, strings.
  • Deliverable — submit the source code and a report structured as in 5report.md; the code must reproduce the example outputs in 4task.md.
  • Self-contained theory — everything needed is in 2method.md; no external material is required.

Summary

A finite state machine (FSM) reads its input one symbol at a time and keeps a single piece of memory — its current state. Despite this simplicity, an FSM is exactly the right tool for lexical scanning: recognising numbers embedded in arbitrary text. This work builds one scanner in four stages, each extending the machine with more states — from collecting individual digits, to grouping them into integers, to admitting a decimal point (rationals), to admitting a leading sign. The same input string is processed at every stage, so the growing power of the machine is directly visible in the output.

Laboratory/Laboratory8/main.md · 2.4 KB · updated 2026-08-01 17:39