CL - 13b - regex and FSM
From Haoran Peng on November 17th, 2020
We introduce some simple finite state machines, and three key ideas of the theory.
The first idea is that of the language recognised by a machine. Given an alphabet of symbols, a language is a set (often an infinite set) of strings using these symbols as characters. Our machines accept some strings and do not accept others. The set of acccepted strings is the language recognised by the machine
The second idea is that we may describe some sets of strings using patterns known as regular expressions (regex). For the time being we introduce regular expresssions and some simple examples of machines whose language may be described in this way.
The third idea is that we may construct new machines composed of simpler machines. We give a first example, running two machines in parallel, and argue that the language recognised by this machine is the union of the languages recognised by the component machines.