Please note that only content with BLUE titles is exam-related. Other content is basic/background info. Half of the content is based on the course MIT 18.404J Theory Of Computation. The other half(especially exam-related parts) is based on the course Automaten und Sprache.
A language L(A) is called regular if there is a DFA that accepts it. Regular languages are context-free! L(A) = {w∈Σ* | A accepts w} = {w∈Σ* | δ (q0, w)∈F}
— Built from $\Sigma$, members $\Sigma, \phi , \varepsilon$ [Atomic] (no stars)
— By using Operations [Composite]
| Symbol | Meaning |
|---|---|
| . | Any character |
| \d | Any digit |
| \s | Whitespace |
| \w | Alphanumeric character [a-zA-Z_0-9] |
| \ | Escape character, the following character is treated literally (e.g., \“ means the character “ follows) |
| \b | Word boundary |
| ^ | Start of a line / beginning of the text |
| $ | End of a line / end of the text |
| () | Group |
| ? | Occurs 0 or 1 time |
| + | Occurs 1 or more times |
| * | Occurs 0 or more times |
| {n} | Occurs n times |
| {n,m} | Occurs n to m times |
| X | Y |
| r{,3} | r |
| r{2,3} | rr |
| r{3,} | rrr* |
| [0-9] | A digit from 0 to 9 |
| [a-z] | A letter from a to z |
| [a-z]{0,3} | Zero to three letters from a to z |
| [a-zA-Z] | A letter from a to z or from A to Z |
| [12] | A character from the list [12] (i.e., 1 or 2) |
| [^abc] | Any character except a, b, or c |
closure under $\cup$ (Union)
Theorem: if A1, A2 are regular languages, so is $A_{1}\cup A_{2}$
Proof: let
$$ M_{1} = (Q_1,\Sigma_1,\delta_1,q_{1},F_1)\ recognize\ A_1\\ M_{2} = (Q_2,\Sigma_2,\delta_2,q_{2},F_2)\ recognize\ A_2 $$
Construct $M = (Q,\Sigma,\delta,q_0,F)\ recognize\ A_1 \cup A_2$
M should accept input w if either $M_1$ or $M_2$ accept w.
Closure under $\circ$ (concatenation) Theorem: if A1, A2 are regular languages, so is $A_{1} A_{2}$
Closure under $\ast$ (star) Theorem: If $A$ is a regular language, so is $A^\ast$
Theorem: If R is a regular expression and A = L(R) then A is a regular language Proof: Convert R to equivalent NFA M