Foundations — Regular languages — closed under union, intersection, complement, concatenation, Kleene star

Before you can read the parent note, you need to be fluent in a small pile of symbols and pictures. Below, every one is built from zero, in an order where each rests on the one before. Nothing is used before it is drawn.

0. The alphabet $\Sigma$ — the box of letters we are allowed

Picture it as a literal box holding a few letter-tiles.

WHY the topic needs it. Every string, every machine, every language is defined relative to one fixed box of letters. If you change the box, you change the game. When the parent writes "strings over $\{0,1\}$", it means: pull tiles only from this box.

1. A string $w$ — a row of tiles

Picture: a string is a row of tiles laid end to end, read like a word.

WHY the topic needs it. The robots read one string at a time, tile by tile, and the answer YES/NO is about that one string. Strings are the things machines eat.

2. The empty string $\epsilon$ — the row with zero tiles

WHY the topic needs it. Kleene star (Section 5 of the parent) explicitly includes $\epsilon$ ("$k=0$ copies"). The $\epsilon$-transitions used to glue machines are named after exactly this "read no tile" jump.

3. ${\Sigma }^{\ast }$ — the set of ALL possible strings

Picture: an infinite bag containing $\epsilon$, then all length-1 strings, then all length-2 strings, and so on forever.

WHY the topic needs it. ${\Sigma }^{\ast }$ is the universe of everything. Every language lives inside it, and complement is measured against it: $\overline{A}={\Sigma }^{\ast }\setminus A$ means "all strings except the ones in $A$."

4. A language $A$ — a chosen subset of the universe

Picture: draw the big oval ${\Sigma }^{\ast }$; a language $A$ is a circle inside it. Strings inside the circle are the accepted ones; everything outside is rejected.

WHY the topic needs it. The entire question "is this language regular?" is a question about a subset of ${\Sigma }^{\ast }$. Closure operations combine these subsets.

5. Set operations $\cup ,\cap ,\setminus ,\overline{},\subseteq ,\in$ — combining circles

Because languages are sets, we combine them with ordinary set operations. Look at the picture, then read each symbol.

The link De Morgan's Laws is why union is "free" once you have complement and intersection: $A\cup B=\overline{\overline{A}\cap \overline{B}}$ — flip both, overlap, flip back.

6. Concatenation $xy$ and $AB$ — gluing rows of tiles

WHY the topic needs it. Section 4 of the parent (concatenation closure) is literally about $AB$. The example $\{a^n{b}^m\}=\{a{\}}^{\ast }\cdot \{b{\}}^{\ast }$ uses this glue.

7. The machines: DFA and NFA — the robots that say YES/NO

8. The formal machine tuple and its symbols

The parent writes a DFA as $M=(Q,\Sigma ,\delta ,q_0,F)$. Now every letter is earned:

WHY the topic needs it. Every construction in the parent (flip $F$, product states, $\epsilon$-glue) is written in exactly these symbols. Without them the proofs are unreadable.

9. Regular language & regular expression — the "club" itself

Prerequisite map

Equipment checklist

Cover the answers and test yourself. If any line is fuzzy, reread its section.