Difficulty: Intermediate to Advanced | Prerequisites: Familiarity with sets, functions, and basic proof techniques
This set of notes covers DFA construction, reading DFA diagrams, countability of sets, and the decidability/undecidability hierarchy. These topics account for roughly 30-40 points of the EECS 376 midterm. The core skill is classifying languages and sets: can a DFA handle it, can a Turing machine handle it, or is it beyond both?
DFA (Deterministic Finite Automaton)
A machine with a finite number of states, a start state, a set of accept states, and a transition function that maps each (state, symbol) pair to exactly one next state. It reads an input string one symbol at a time and accepts if it finishes in an accept state.
Think of it as a flowchart with no memory beyond which box you are currently in.
Regular language
A language that can be decided by some DFA. Equivalently, a language that can be described by a regular expression. Regular languages are closed under union, intersection, complement, and concatenation.
Countable set
A set is countable if its elements can be listed in a sequence (put in one-to-one correspondence with the natural numbers), or if it is finite. The set of all integers is countable. The set of all real numbers is not.
In simple terms, countable means you could, in principle, write down every element in a numbered list, even if the list is infinite.
Uncountable set
A set that is too large to be listed. The classic example is the set of all subsets of the natural numbers, or equivalently the set of all languages over {0,1}.
Decidable language
A language L is decidable if there exists a Turing machine that, on every input, halts and correctly outputs "accept" or "reject." The machine always terminates.
Undecidable language
A language for which no Turing machine can both always halt and always give the correct answer. The halting problem is the canonical example.
Recognisable (recursively enumerable) language
A language L is recognisable if there exists a Turing machine that accepts every string in L and either rejects or loops forever on strings not in L. Every decidable language is recognisable, but not every recognisable language is decidable.
Turing machine
A theoretical model of computation with an infinite tape and a finite set of states. It can read, write, and move left or right on the tape. Turing machines are strictly more powerful than DFAs because they have unbounded memory.
Reading a DFA diagram (Exam Q4)
The exam gives a DFA with states q0 (start), q1, q2, q3, and qr (accept, shown with a double circle). Transitions:
q0 on 0 goes to q1, on 1 goes to qr.
q1 on 0 stays at q1 (self-loop), on 1 goes to q2.
q2 on 0 goes to q3, on 1 stays at q2 (self-loop... wait, let me re-examine).
Actually, from the diagram: q2 on 1 goes to q3 (based on the arrow), and q3 on 0 goes to qr. qr on 0 or 1 stays at qr (self-loop on both).
Let us trace some strings:
Empty string ε: stay at q0. q0 is the start state. Is q0 an accept state? Looking at the diagram, qr is the only accept state (double circle). So ε is rejected.
"001": q0 -0-> q1 -0-> q1 -1-> q2. Not in qr. Rejected.
"0010": q0 -0-> q1 -0-> q1 -1-> q2 -0-> q3. Not in qr. Rejected.
"00100": ...-> q3 -0-> qr. Accepted.
The pattern (001)* would mean strings like ε, 001, 001001, etc. But ε is rejected (we end at q0, not qr). So (001)* is wrong.
For 0*(01): the 0 part loops in q1 (after the first 0 takes us from q0 to q1, further 0s stay in q1). Then each "01" from q1 would go q1 -0-> q1 -1-> q2. But we need to reach qr, and from q2 we need a 0 to reach q3, then another 0 to reach qr. This does not match 0*(01)*.
The correct answer is (001). The empty string must be tested carefully: since the DFA starts at q0 and (001) includes ε, we need q0 to be an accept state for this to work. But q0 is not the accept state. This means none of the listed languages match, and the answer is None of these languages are decided by the DFA.
Constructing a DFA (Exam Q10)
The task: build a DFA over {a, b, c} with at most 7 states that accepts strings containing at least two occurrences of the substring "abc."
The standard approach is to track your progress through matching "abc". You need states for:
How far along you are in matching the current "abc" (0, 1, or 2 characters matched).
How many complete "abc" substrings you have found so far (0, 1, or 2+).
This gives a state for each combination of (matches found so far: 0 or 1) x (progress in current match: 0, 1, or 2 characters), plus a final accept state for "2 found."
That is 2 x 3 + 1 = 7 states, which fits the budget.
State labels (found, progress): (0,0), (0,a), (0,ab), (1,0), (1,a), (1,ab), ACCEPT.
Transitions from state (0,0):
On 'a': go to (0,a).
On 'b' or 'c': stay at (0,0).
Transitions from state (0,a):
On 'a': stay at (0,a) (the new 'a' could start a fresh match).
On 'b': go to (0,ab).
On 'c': go back to (0,0).
Transitions from state (0,ab):
On 'a': go back to (0,a).
On 'b': go back to (0,0).
On 'c': first "abc" found, go to (1,0).
The (1,) states mirror the (0,) states, except that from (1,ab) on 'c', you go to ACCEPT.
ACCEPT is absorbing: all transitions from ACCEPT go back to ACCEPT.
Countability questions ask you to decide whether a given set can be put in one-to-one correspondence with the natural numbers.
Key facts to memorise
The set of all Turing machine encodings {⟨M⟩ : M is a TM} is countable. Every TM can be encoded as a finite binary string, and the set of all finite binary strings is countable.
The set of all (⟨M⟩, x) pairs where M accepts x is countable. It is a subset of pairs of finite strings, and the set of all finite-string pairs is countable.
Any subset of a countable set is countable.
The set of all languages over {0,1} is uncountable. Each language is a subset of {0,1}*, and the power set of a countably infinite set is uncountable (by a diagonalisation argument).
The set of all undecidable languages over a given alphabet is uncountable. There are uncountably many languages but only countably many Turing machines, so almost all languages are undecidable.
A set that is described as a set of finite objects (strings, pairs of strings, TMs) is typically countable. A set that is described as a set of languages (each of which is itself a set of strings) is typically uncountable.
Exam Q6 walkthrough
{⟨M⟩ : M is a Turing machine}: Countable. TMs have finite encodings.
{(⟨M⟩, x) : M accepts x}: Countable. Each element is a finite pair.
{L : |L| is finite and L is undecidable}: This set is empty, because every finite language is decidable (you can hardcode every string). An empty set is countable (it is finite).
{L : L ⊆ {0,1}*}: This is the set of ALL languages over {0,1}. Uncountable.
The set of all undecidable languages over Σ = {1}: Uncountable. There are uncountably many languages over {1} (same power-set argument) and only countably many are decidable.
Countable sets: the first three.
The exam tests whether you can classify languages about Turing machines as decidable or undecidable. The general rule: if answering the question requires running a TM for an unbounded number of steps, it is likely undecidable. If you can answer it by simulating for a bounded number of steps, it is decidable.
Exam Q7 walkthrough
L_280 = {⟨M⟩ : M rejects at least 280 different input strings}: Undecidable. To determine whether M rejects at least 280 strings, you would need to test M on infinitely many inputs. On some of those inputs, M might loop forever, so you cannot always determine whether M rejects them. This is a non-trivial semantic property of TMs, so by Rice's Theorem it is undecidable.
L_203HALT = {(⟨M⟩, x) : M halts on x after at least 203 steps}: Decidable. Simulate M on x for 203 steps. If M has not halted by step 203, accept (it will run for at least 203 steps whether or not it eventually halts). If M halts in fewer than 203 steps, reject. This simulation always terminates in at most 203 steps.
L_281ACC = {(⟨M⟩, x) : M accepts x in strictly less than 282 steps}: Decidable. Simulate M on x for 281 steps. If M accepts within that window, accept. Otherwise, reject. Bounded simulation always halts.
L_376 = {⟨M⟩ : M accepts 101111000}: Undecidable. This asks whether M accepts a specific string. You cannot just simulate M on 101111000 because M might loop forever on that input. This is equivalent to the acceptance problem restricted to a fixed input, which is still undecidable.
L_482ACC = {⟨M⟩ : M accepts every input in exactly 482 steps}: Decidable. For any fixed M, run it on all inputs for 482 steps. Wait: there are infinitely many inputs. But the key insight is that a TM's behaviour in exactly 482 steps depends only on the first 482 symbols of the input (the head cannot move more than 482 cells). So there are only finitely many distinct behaviours to check. You can enumerate all relevant input prefixes and simulate each for 482 steps.
Undecidable languages: L_280 and L_376.
Some languages require more than finite memory to decide, but a Turing machine (with its infinite tape) handles them just fine. The exam asks you to identify these.
Exam Q8 walkthrough
L_Count = {0^n 1^n 2^n | n >= 0}: Not regular (a DFA cannot count three groups and compare their sizes). Decidable by a TM that marks off one 0, one 1, and one 2 at a time. Correct selection.
L_Double = {ww | w in {0,1}*}: Not regular (a DFA cannot remember an entire first half). Decidable by a TM that finds the midpoint, then compares the two halves symbol by symbol. Correct selection.
L_Prime = {⟨n⟩ : n is a prime number}: Not regular (the primes are not eventually periodic, and no DFA can check primality of arbitrarily large numbers). Decidable by a TM that performs trial division. Correct selection.
L_Loop = {(⟨M⟩, x) : M loops on x}: Not decidable. This is the complement of the halting problem. If you could decide L_Loop, you could decide the halting problem (M halts on x iff (M, x) is not in L_Loop). Since HALT is undecidable, L_Loop is undecidable too. Not a correct selection.
L_Palindrome = {⟨s⟩ : s is a palindrome}: Not regular (a DFA cannot remember the entire first half to compare with the reversed second half). Decidable by a TM that compares the first and last characters, removes them, and repeats. Correct selection.
Correct answers: L_Count, L_Double, L_Prime, L_Palindrome.
Proving a language is not regular (Exam Q12)
The balanced parentheses language L_BAL = {w in {(,)}* : w is balanced} is not regular. The standard proof uses a counting/pigeonhole argument (sometimes called the Pumping Lemma approach).
Proof sketch: Assume for contradiction that some DFA D with p states decides L_BAL. Consider the strings ( ^1, ( ^2, ..., ( ^(p+1). These are p+1 distinct strings. By the pigeonhole principle, two of them, say ( ^i and ( ^j with i < j, must reach the same state in D.
Since D reaches the same state after reading ( ^i and ( ^j, it must behave identically on any continuation. In particular, consider appending ) ^i. The string ( ^i ) ^i is balanced (in L_BAL), so D must accept it. But then D also accepts ( ^j ) ^i, which has j opening parens and only i closing parens. Since j > i, this string is not balanced, so it should be rejected. Contradiction.
Therefore no DFA can decide L_BAL.
Students often think that if you can decide membership for a specific string, the language is decidable. That is wrong. L_376 asks whether M accepts a specific string, but the question is about all possible M, not a specific one. For a given M, you may loop forever trying to simulate it.
"Finite language" and "finite set" are different concepts in this context. A finite language (finitely many strings) is always decidable. A finite set of TMs is countable. But the set of all languages, each of which is itself an infinite object, is uncountable.
The complement of a decidable language is always decidable (just flip accept and reject). The complement of a recognisable-but-undecidable language is not recognisable.
Students sometimes think any language involving numbers must be non-regular. Some number languages are regular: for instance, "binary strings divisible by 3" is regular because you can track the remainder mod 3 with a DFA. The issue arises when you need to compare or count unbounded quantities.
When constructing a DFA, students often forget to handle all transitions. Every state must have exactly one transition for every symbol in the alphabet. Missing transitions mean your DFA is incomplete.
⚠️ The "select all" questions on countability and decidability are worth 5 points each, with a 2-point penalty per error. Getting one wrong costs you, so only select options you are confident about.
⚠️ DFA construction (Q10) is worth 8 points and is easy to lose marks on if you miss a transition. Draw the full transition table before committing to the diagram.
⚠️ The pumping lemma / pigeonhole proof (Q12) is a standard template. Memorise the structure: assume a DFA exists, pick a family of strings that force the DFA into a pigeonhole collision, then show the collision leads to a contradiction.
⚠️ For decidability (Q7), the quick test is: can you answer the question about M by running M for a bounded number of steps? If yes, decidable. If no, likely undecidable.
True or False: The set of all languages over {0,1} is countable. (False: it is uncountable.)
True or False: Every finite language is decidable. (True.)
Fill in the blank: A language L is decidable if there exists a Turing machine that ______ on every input. (halts)
True or False: {⟨M⟩ : M accepts 101111000} is decidable because you can just simulate M on that string. (False: M might loop forever on that input.)
True or False: The language {ww | w in {0,1}*} can be decided by a DFA. (False: a DFA cannot remember an entire first half.)
Q: Is the language {⟨M⟩ : M halts on all inputs of length at most 5} decidable?
A: Yes. There are finitely many strings of length at most 5. For each such string x, simulate M on x. Since there are finitely many inputs and we need M to halt on all of them, we can dovetail: simulate step 1 of M on each input, then step 2, and so on. If M halts on all of them, we eventually see every one halt. If M loops on any one, we loop forever, but that means M does not halt on all, so we need to be more careful. In fact, this language is recognisable but the question of decidability is more subtle. Actually, this language is not decidable: for any single input, we cannot decide if M halts (the halting problem). The fact that there are finitely many inputs does not help because we still need to determine halting for each one. Correction: this is undecidable.
Q: Construct a regular expression for the language decided by a DFA that accepts all binary strings with an even number of 1s.
A: 0*(1010)* - this matches any number of leading 0s, followed by pairs of 1s separated by any number of 0s.
Q: Is the set {⟨M⟩ : M is a TM that accepts at least one string} countable?
A: Yes. Every element is a TM encoding (a finite string), and the set of all finite strings is countable. Any subset of a countable set is countable.
Q: Prove that {0^n 1^n | n >= 0} is not regular.
A: Assume a DFA with p states decides this language. Consider the p+1 strings ε, 0, 00, ..., 0^p. By pigeonhole, two of them (say 0^i and 0^j, i < j) reach the same state. Append 1^i. The DFA accepts 0^i 1^i (which is in the language) and therefore also accepts 0^j 1^i (which is not, since j > i). Contradiction.
DFAs and regular languages connect forward to the computability hierarchy: regular ⊂ context-free ⊂ decidable ⊂ recognisable ⊂ all languages. The exam primarily tests the endpoints (regular vs. decidable vs. undecidable) rather than the middle.
Countability connects to the existence of undecidable problems. The argument is simple: there are countably many TMs but uncountably many languages, so most languages have no TM at all.
The pigeonhole-style proof for showing a language is not regular (Q12) uses the same structural argument as the Pumping Lemma, which you may see in more detail in EECS 376 homework or in a theory-of-computation course.
Related Terms / Search Tags
DFA, deterministic finite automaton, NFA, regular language, regular expression, context-free language, countable, uncountable, Cantor, diagonalisation, decidable, undecidable, recognisable, recursively enumerable, Turing machine, halting problem, Rice's Theorem, pumping lemma, pigeonhole principle, EECS 376, Foundations of Computer Science, University of Michigan, Winter 2026 midterm