Regular expressions — equivalence with finite automata: Question bank

True or false — justify

Every line: decide true/false, then give the why.

True or false: A regex and the NFA built from it by Thompson's construction accept exactly the same set of strings.

True. Thompson's construction is proven correct by induction on the regex structure, so the gadget's language equals the sub-regex's language at every step, up to the whole pattern.

True or false: If a language is regular, there is exactly one regex that describes it.

False. Infinitely many equivalent regexes describe the same language (e.g.

a b^{*}

and

a ∣ ab b^{*}

), just as

2 + 3

and

3 + 2

name the same number.

True or false: Every finite automaton can be converted to a regex, but some regexes are too complex to convert to a finite automaton.

False. The iff goes both ways with no exceptions; every regex has an equivalent NFA (Thompson) and every FA has an equivalent regex (state elimination).

True or false: Because NFAs allow

ε

-transitions and DFAs do not, NFAs recognize strictly more languages than DFAs.

False. Subset construction shows NFA ≡ DFA in power;

ε

-moves add convenience, not new languages.

True or false: The regex

\emptyset

and the regex

ε

describe the same language.

False.

\emptyset

is the empty language

{}

(accepts nothing, not even the empty string);

ε

{ε}

, the language containing exactly the empty string.

True or false: In Thompson's construction the final NFA always has exactly one accept state.

True. The whole point of the single-start/single-accept invariant is to make gluing trivial; every gadget preserves it, so the top-level machine has one accept state.

True or false: The self-loop term

R_{q q}^{*}

in the state-elimination rule can be dropped when the eliminated state has no self-loop.

True (in effect). With no self-loop,

R_{q q} = \emptyset

and

\emptyset^{*} = ε

, which is the identity for concatenation, so the term simply vanishes.

True or false: A language recognized by a finite automaton can always be described by a finite-length regex.

True. State elimination removes finitely many states, each producing a finite regex, so the surviving label

R_{s f}

is always finite text — even when the language it names is infinite.

True or false: If two GNFA state-elimination orders give textually different regexes, at least one order made a mistake.

False. Different orders legitimately yield different-but-equivalent regexes for the same language; correctness is judged by the language, not the text.

True or false: Since regexes and DFAs are equivalent, the pumping lemma can be used to prove a regex cannot describe a given language.

True. If no DFA accepts

L

(shown via pumping), then by the equivalence no regex describes

L

either — the lemma bites regexes indirectly.

Spot the error

Each item states a flawed claim or construction. Find the flaw.

"I'll merge the star gadget's new start with

N_{R}

's start to save a state."

The invariant "no edges into start, no edges out of accept" breaks; a leaked loop-back edge can accept a string that is not a clean repetition of

R

. Always add fresh start/accept for star and union.

"For concatenation

R S

, I keep

N_{R}

's accept state accepting AND make

N_{S}

's accept accepting too."

Wrong —

N_{R}

's old accept must stop being accepting; otherwise the machine accepts strings that only match

R

without the required

S

part following.

"State elimination gives regex

a b^{*}

; therefore the machine rejects the empty string, since

a b^{*}

needs at least one

a

The reasoning about

a b^{*}

is fine, but this is only a property of that language; don't confuse "this regex requires an

a

" with a general rule — a different machine's regex might match

ε

via a

^{*}

at the outer level.

R^{*}

means 'one or more copies of

R

', so the star gadget needs no skip-edge."

R^{*}

means zero or more; the skip-edge (new start

ε

new accept) is exactly what allows the zero-copy case, i.e. accepting

ε

"To convert an NFA with several accept states to a regex, I just eliminate states in any order and read off the label — no setup needed."

You must first normalize: add a fresh start with

ε

into the old start, and a fresh accept with

ε

from every old accept. Skipping this leaves multiple accepts and edges out of the start, and the ripping rule no longer applies cleanly.

\emptyset^{*} = \emptyset

, because zero copies of nothing is still nothing."

\emptyset^{*} = ε

. "Zero or more copies" always includes the zero case, which is the empty string

ε

, regardless of what you're starring.

"Thompson gives an NFA; NFAs are weaker, so to be safe I should also add the pumping lemma to prove the regex is regular."

A regex defines a regular language by definition — no proof of regularity is needed. Thompson merely exhibits the machine; the pumping lemma is a tool for the opposite job (showing something is not regular).

Why questions

Why do we prove regex ↔ NFA rather than regex ↔ DFA directly?

NFAs with

ε

-moves glue together beautifully in Thompson's construction; since NFA ≡ DFA is already known, proving the easier NFA case gives the DFA case for free.

Why were regex operators chosen to be exactly union, concatenation, and star?

They mirror the three things

ε

-transitions let an NFA do — branch (union), sequence (concatenation), and loop back (star) — which is precisely why the equivalence comes out so clean.

Why does the ripping rule use the pattern

R_{i q} R_{q q}^{*} R_{q j}

rather than

R_{i q} R_{q j}

A path through

q

may spin on $q$ 's self-loop any number of times before leaving;

R_{q q}^{*}

captures "zero or more spins," which a bare

R_{i q} R_{q j}

would miss.

Why does the ripping rule keep the old

R_{ij}

with a "

∣

" (union) rather than overwriting it?

There may already be a direct route

i \to j

that bypasses

q

entirely; the union preserves that alternative alongside the new route through

q

Why must the normalized GNFA have no edge into the start and none out of the accept?

So that when only start and accept survive, there is a single clean edge between them whose label is unambiguously the whole language's regex — no stray loops or entries to account for.

Why does the star gadget loop

N_{R}

's accept back to

N_{R}

's start instead of to the new start?

Looping to

N_{R}

's own start re-enters exactly one fresh copy of

R

; routing to the new start would risk re-taking other branches and corrupt the "clean repetition of

R

" meaning.

Why is the closure of regular languages under union, concatenation, and star essentially the same fact as Thompson's construction?

Each Thompson gadget is a constructive proof that regular languages are closed under that operation — building the combined machine is the closure argument.

Edge cases

What NFA does Thompson build for the regex

\emptyset

, and what does it accept?

A start state and an accept state with no path between them; it accepts the empty language

{}

— no string at all, not even

ε

What regex does state elimination give for a machine whose start state is also its only accept state and has no transitions?

After normalization the only surviving label is

ε

(the

ε

edges into and out of the single old state chain through), so the regex is

ε

— accepting exactly the empty string.

What happens in Thompson's construction if the alphabet symbol

a

appears but we build no gadget for it?

You cannot — every symbol

a \in Σ

used in the regex must contribute its base gadget

\to a \to

; omitting it means the pattern was never fully translated, so the induction is incomplete.

For

R^{*}

, does the built NFA accept the empty string

ε

Yes — the skip-edge from the new start directly to the new accept is the "zero copies" path, which accepts

ε

regardless of what

R

is.

If a DFA accepts every string over

Σ = {a, b}

, what regex does elimination produce, and is it unique?

A regex equivalent to

(a ∣ b)^{*}

(all strings); it is not textually unique —

(a ∣ b)^{*}

(b ∣ a)^{*}

(a^{*} b^{*})^{*}

all name the same universal language.

What is the regex for a DFA with a start state that is not accepting and no accepting states reachable?

\emptyset

— with no accepting path surviving normalization, the label between new start and new accept is the empty language, correctly meaning "accepts nothing."

How does the empty string

ε

differ from a self-loop labeled

ε

during elimination?

A plain

ε

edge is just a free hop between distinct states; a self-loop labeled

ε

contributes

ε^{*} = ε

to the rule, adding nothing — starring the empty string still gives only the empty string.

Recall One-line self-check before you move on

Can I explain, without notes, why different elimination orders are all correct? ::: They produce equivalent regexes (same language, different text); correctness is judged by the language recognized, exactly like $2 + 3 = 3 + 2$ .