Regular expressions — equivalence with finite automata: Foundations

The parent topic throws a lot of notation at you in the first paragraph. Here we slow all the way down. Each item below gives you three things: plain words, the picture, and why the topic needs it. They are ordered so every symbol is built only from symbols already defined.

1. The alphabet $Σ$ and a "string"

The picture: think of $Σ$ as the set of tiles in your Scrabble bag, and a string as one row you laid down.

Figure — Regular expressions — equivalence with finite automata

Cloze check: The set of allowed symbols is called the alphabet and written == $Σ$ ==.

2. The empty string $ε$

The picture: $ε$ is an empty Scrabble rack — you laid down nothing at all, but "nothing" is still a legal thing to have laid down.

3. A language: the empty language $\emptyset$

The picture: a language is a guest list. $\emptyset$ is a party where nobody is on the list — not even the empty-handed guest $ε$ .

4. Three ways to combine languages: $\cdot$ , $∣$ , $^{*}$

These are the operators that turn small patterns into big ones. Each is a set operation on languages, and each mirrors one thing a machine can do. We define them once here so the parent's regex syntax reads cleanly.

The picture below shows all three operators as actions on bags of strings.

5. A finite automaton: states and arrows

Now the machine side. We build its picture from parts.

For the meaning of DFA vs NFA (one path vs many possible paths at once), see Finite Automata — DFA and NFA. For $ε$ -arrows specifically — arrows you take without eating a symbol — see Epsilon-NFA and epsilon-closures.

6. The $ε$ -transition (the glue)

The picture: it is a secret trapdoor between two rooms — you can slip through without laying down a tile.

7. The proof word: $⟺$ (if and only if)

The picture: a two-way bridge. Kleene's Theorem says regex-land and machine-land are connected by a bridge you can cross both ways: regex $\to$ machine (Thompson) and machine $\to$ regex (state elimination).

The prerequisite map

Related deeper topics once you are through the door: Subset Construction — NFA to DFA equivalence, Regular Languages — closure properties, Pumping Lemma for Regular Languages, and the real-world payoff in Lexical analysis and grep — applications.

Equipment checklist

Cover the right side and answer out loud; reveal to check.

What does the symbol Sigma stand for? ::: The alphabet — the finite set of allowed symbols. What is a string? ::: A finite left-to-right row of symbols from Sigma. What is epsilon? ::: The empty string — zero symbols, still a valid word. Difference between {ε} and ∅? ::: {ε} has one string (the empty one); ∅ has no strings at all. What is a language? ::: A set of strings (a bag of allowed words). What does R S (concatenation) do? ::: Glues a word from R in front of a word from S. What does R | S mean? ::: Union — a word in R or in S. What does R* mean, and does it include ε? ::: Zero or more concatenated copies of words in R; yes, always includes ε. How is a start state marked? ::: An incoming arrow from nowhere. How is an accept state marked? ::: A double circle. When is a string accepted by an FA? ::: When reading it ends in an accept state. What does an ε-transition let a machine do? ::: Change state for free, without consuming a symbol. What must you prove for an "iff" statement? ::: Both directions separately. Which three machine moves do concat, union, star mirror? ::: Sequence one then another, branch/choose, loop to repeat.