Test 1 (Part 1): Regular Languages & Finite Automata Summary & Study Notes

📚 Vocabulary — Core terms you must know

Alphabet: a finite set of symbols (often denoted $\Sigma$). A string is a finite sequence of symbols from $\Sigma$ and the length of a string $s$ is $|s|$. A language is a set of strings over $\Sigma$.

Finite automaton (FA): a 5-tuple with states, alphabet, transition function, start state, and accepting states. Deterministic finite automaton (DFA): at most one transition per state and symbol. Nondeterministic finite automaton (NFA): may have multiple transitions and $\epsilon$-transitions.

Regular language: a language recognized by some FA (equivalently described by a regular expression). Regular expression (RE): algebraic description of a regular language using union, concatenation, and Kleene star.

Transition function, accepting (final) state, reachable state, equivalent states, epsilon-closure, pumping length — know definitions and how to use them.

🔁 Constructions & Procedures — what to be able to do

Construct a FA: design states representing progress through required constraints; mark accepting states for satisfied conditions. Keep constructions minimal and justify transitions.

Union / concatenation / star: build NFAs (or DFAs via product/other construction) that combine machines. For union use nondeterministic choice or product construction for DFAs; for intersection use the product construction where states are pairs and transition is pairwise.

Show a FA accepts a string: simulate the automaton on the string. For a DFA follow the unique path; for an NFA show a sequence of transitions (or compute reachable set/epsilon-closures) that ends in an accepting state.

NFA -> DFA (subset construction): states of the DFA are subsets of NFA states; start is epsilon-closure of NFA start; transitions map subsets under input symbol then take epsilon-closure. Be able to perform this step-by-step.

DFA equivalence / checking two automata equivalent: construct the symmetric difference (via product automaton) and check emptiness of the resulting language (i.e., reachable accepting state?). If empty, automata equivalent.

Convert FA -> regular expression (state-elimination): systematically eliminate states, updating transition regex labels until only start and final remain; resulting label is the desired RE. Know the elimination idea and practice on small examples.

Convert RE -> FA (Thompson’s construction): build small NFAs for base cases and combine using concatenation/union/star templates.

🔬 Key Theorems & Properties — statements and how to use them

Closure properties of regular languages: Regular languages are closed under union, concatenation, Kleene star, intersection, and complement. Use closure to build or reason about languages and to construct counterexamples.

Equivalence of DFAs and NFAs: For every NFA there exists a DFA recognizing the same language (subset construction). Use this to move between models freely.

Equivalence of regular expressions and regular languages (RE <-> FA): For every RE there is an NFA that recognizes the same language (Thompson), and for every FA there is an RE that describes its language (state elimination).

Pumping Lemma for regular languages (use to prove non-regularity): If $L$ is regular then there exists pumping length $p$ such that for any $s\in L$ with $|s|\ge p$ we can write $s = xyz$ with $|xy|\le p$, $|y|>0$, and for all $i\ge 0$ we have $xy^iz\in L$. To show non-regularity, assume regular, pick $p$, choose a specific $s$ with $|s|\ge p$, and derive a contradiction by showing some pumped string is not in $L$.

Finiteness vs infiniteness for regular languages: A regular language recognized by a DFA is infinite iff there exists a path from the start to a reachable state that lies on a cycle and from that cycle you can reach an accepting state. Practically, check for loops on paths to accepting states.

Deciding equivalence of two finite automata: Two FAs are equivalent iff their symmetric difference recognizes the empty language. Construct product automaton and test for reachable accepting states. This yields a mechanical procedure to decide equivalence.

✅ Practical exam tips (one-sheet essentials)

Write down definitions of DFA, NFA, regular expression, and regular language. Include the subset construction steps, the state-elimination outline, and the Pumping Lemma statement with the quantifiers. Add short procedural checklists: simulate FA on string, build union/intersection machine, check equivalence via product and emptiness.

Keep examples: a tiny NFA -> DFA conversion, a small state-elimination step, and one pumping-lemma style non-regularity proof skeleton.

📝 Summary from your prompt — focused checklist

This source lists the exact scope for Test 1. Make sure you can: define all vocabulary from Chapter 1 (DFA, NFA, regular language, regular expression), and apply the theorems we covered.

Be prepared to: construct finite automata (including for union and intersection), show a finite automaton accepts a given string (simulate or show accepting path), convert an NFA to a DFA (subset construction), convert an FA to a regular expression (state elimination), and convert a regular expression to an FA (Thompson’s construction).

Know closure properties: union, concatenation, star, intersection, complement. Know the Pumping Lemma and the methods to prove finiteness/infiniteness and equivalence of two finite automata.

Use your one sheet to write concise definitions, the pumping-lemma template, subset-construction checklist, product-construction checklist for intersection/equivalence, and the state-elimination pattern — these will cover nearly all problems listed.