Week 9

Reading

Chapter 28, Regular Expressions.

Chapter 29, Regex and Machines.

Chapter 30, Deterministic Finite Automata.

Chapter 31, Nondeterministic Finite Automata.

Use the FSM workbench to get familiar with FSM by completing some or all of the following exercises (the *'d ones are definitely optional):

This week's videos introduce you to FSMs and their implementation in Haskell.

Machines

This video introduces the notion machine.

Slides (1..18)
Video (5:08)
regex and FSM

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.

Slides (19..20)
Video (7:20)
Machines in Haskell

In this video we formalise the definition of an FSM, describe how a machine and its behaviour may be represented in Haskell.

In this video we use lists to represent the sets used in the mathematical definition. In the code for tutorials we use the same ideas, but using Haskell's Data.Set library to represent these sets.

Slides (15..16)
Video (9:34)
Black holes and DFA

We begin with a short discussion of the history and some applications of FSM. We then introduce Deterministic Finit-state Automata (DFA), and the use of the black hole convention when presenting DFA.

In this video we use lists to represent the sets used in the mathematical definition. In the code for tutorials we use the same ideas, but using Haskell's Data.Set library to represent these sets.

Slides (15..16)
Video (3:32)
Machines in Haskell (II)

In this video we present the formalisation of the accepts function in Haskell.

In this video we use lists to represent the sets used in the mathematical definition. In the code for tutorials we use the same ideas, but using Haskell's Data.Set library to represent these sets.

Slide (8)
Video (3:04)
Regular Languages (I)

We give a first definition of regular language as a language that is accepted by some FSM.

Slide (8)
Video (2:23)
Regular Languages (II)

We give a second definition of regular language as the languages generated from the empty and singleton languages by the operations of, concatenation, alternation, and iteration.

Slide (9..11)
Video (7:08)
DFA (II)

We look at the representation of DFA in Haskell (using lists to represent the sets of the formal definition).

In this video the code isDFA is defining what counts as a DFA when we use the black-hole convention: it has a single start state and at most one a-labelled transition from any state q.

In the tutorial exercise you are asked to define when an FSM is a DFA in the strict sense that for each symbol a and state q there is exactly one a-labelled transition from q.

Slide (12..16)
Video (5:12)