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):Our third definition: we say a language is DFA-regular if it is the language recognised by some DFA.
We show that the complement of a DFA-regular language is DFA-regular.
Since DFA-regular languages are closed under complements and intersections, they are closed under all Boolean operations.
We introduce NFA - automata with ε-transitions
We present a first example of the use of ε-transitions to concstruct new mahines, and pose a problem to be answered in the following video.
We use ε-transitions to connect two NFA and create a machine that recognises the concatenation of their languges.
Slide 33 describes the construction for R|S.
We construct an NFA for R*; then summarize the algebra of regular expressions.
This is a raw video from 2019. I've not yet had time to edit it into chunks. If you have any questions, or find any errors, please let me know on Piazza.
This video begins with a recap of the definitions of regular language, regex, DFA, FSM, and NFA (aka ε-FSM) (slides 1 — 7)
We then introduce the idea of superstates, which is the basis of the all-important powerset construction (slides 8 — 11).
The remainder of the video uses the FSM workbench to work through some examples of the construction (slides 12 — 29).
This is a raw video from 2019. I've not yet had time to edit it into chunks. If you have any questions, or find any errors, please let me know on Piazza.
The first 35 minutes deal with Arden's lemma. You will sometimes need to use this to derive the regex recognised by a machine.
The following 18 minutes (35:04 — 53:00) reviows some topics concerning NFA, DFA and regex.
Firstly Thompson's construction of an NFA recognising a given regex (slide 18); then a variant of that construction (slide 19). You will need to be able to perform one of these constructions by hand, for very simple examples.
Then a few slides (20 — 24) to recap the definitions of FSM, DFA, NFA, and the languages they accept.<\p>
The final slides (25, 26) give some examples you can use for revision.
This is a raw video from 2019. I've not yet had time to edit it into chunks. If you have any questions, or find any errors, please let me know on Piazza.
This is a revision video.
It begins with a recap of the Thompson construction, and our variant of that construction(slides 2,3).
The next few slides (5 — 9) work through some example questions on machines and regex.
We then turn (slides 10 — 16) to the product and sum constructions for DFA. One important remark concerns the black-hole convention -- for the product construction we may ignore any black hole state; for the sum construction we must explicitly instantiate any black-hole state.
The final slides (17 — 23) work through some example questions. To get the most benefit from thses slides you should attempt the questions before watching this section.