Text & documents

Numbers & maths

Data & formats

Security

Development & DevOps

Artificial Intelligence

Finance

Health & Wellness

Productivity

Games & Entertainment

Multimedia & design

Business

What it is

Automata and formal languages exercises solved step by step: from a regular expression to an NFA (Thompson), from the NFA to a DFA (subset construction), the minimal DFA and the CYK algorithm. At every step you see what is computed and why, which is what an exam asks you to write.

The conventions, with their source

Everything follows the Dragon Book (Aho, Lam, Sethi, Ullman, §3.7) as taught in the open slides of the University of Pisa: Thompson numbers the start state before the children and merges states when concatenating (that is why (a|b)*abb gives 0–10); DFA states are named A, B, C… in the order they are discovered, and the empty set is not a state (you can add the dead state, as Hopcroft and Ullman do). CYK follows Hopcroft, Motwani and Ullman: X(i,j) with indices from 1.

Expression → NFA

NFA → DFA

Minimize

CYK

Problem

Regular expression

One-letter or one-digit symbols; | union, * closure, + one or more, ? optional, parentheses and ε.

Each piece numbers its start state before its children and its final state after them; when concatenating, the final state of the first is the start state of the second (no ε).Aho et al. §3.7.4 · Pisa PLP-05

Trace

N(a): two states, 2 and 3, joined by “a”.

Step 1 of 7 N(a): two states, 2 and 3, joined by “a”.

Concatenation is not a step: it creates no states, it only joins the end of one piece to the start of the next.

NFA with 11 states; start 0, final 10.

The whole thread:the CMOS inverterthe logic gatethe assembly programthe operating systemthe automata (you are here)