"Regular Expressions & Finite Automata" — Practice

Question 1

What is the minimum number of states in a DFA over {a, b} accepting strings whose length is divisible by 4?

Accepted Answer

C

Question 2

Which string is NOT matched by the expression a(a plus b) star b?

Accepted Answer

D

Question 3

Regular languages are closed under all of the following EXCEPT

Accepted Answer

D

Question 4

An NFA over {0, 1} has states p and q, start p, accepting q, with transitions from p on 0 to {p, q}, from p on 1 to {p}, and from q on 1 to {q}. Convert it to a DFA and give the number of reachable states.

Accepted Answer

Apply the subset construction, starting from the set containing only the start state.

State {p}. On 0 the NFA can move to p or q, giving {p, q}. On 1 it can only stay at p, giving {p}.

State {p, q}. On 0: from p we reach {p, q}; from q there is no 0 transition, contributing nothing. The union is {p, q}. On 1: from p we reach {p}; from q we reach {q}. The union is {p, q}.

No further subsets are generated, so the reachable states are {p} and {p, q}, giving 2 reachable states out of the 4 possible subsets.

Accepting states are those containing q, so only {p, q} accepts.

The resulting DFA stays in {p} while reading 1s and moves permanently to {p, q} on the first 0. The language is therefore all strings containing at least one 0.

The instructive point is that only 2 of 4 subsets were reachable. The exponential bound of 2 to the n is a worst case, and typical conversions generate far fewer states because most subsets are never produced by any input.

Question 5

A DFA has states {1, 2, 3, 4}, start 1, accepting {4}, with transitions: 1 to 2 on a and 3 on b; 2 to 2 on a and 4 on b; 3 to 3 on a and 4 on b; 4 to 4 on both. Minimise it.

Accepted Answer

First check reachability. From 1 we reach 2 and 3; from 2 and 3 we reach 4. All four states are reachable.

Now apply table filling. Mark every pair with exactly one accepting state: (1,4), (2,4) and (3,4).

The unmarked pairs are (1,2), (1,3) and (2,3).

Round 1. For (1,2): on a they go to 2 and 2, the same state, so no distinction; on b they go to 3 and 4, which is the marked pair (3,4). Mark (1,2).

For (1,3): on a they go to 2 and 3, the unmarked pair (2,3); on b they go to 3 and 4, which is marked. Mark (1,3).

For (2,3): on a they go to 2 and 3, the pair (2,3) itself; on b they both go to 4, the same state. Nothing forces a mark.

Round 2. Re-examine (2,3). Its successors are (2,3) and (4,4), neither of which is a marked distinguishing pair. No mark.

A full pass produced nothing new, so the algorithm terminates.

Merge states 2 and 3. The minimal DFA has three states: {1}, {2,3} and {4}.

A check: state 1 is distinguished from the merged state because reading b from 1 gives a non-accepting state while reading b from 2 or 3 gives the accepting state 4.

Question 6

Explain why the language of strings over {a, b} whose third symbol from the end is a needs only 4 NFA states but 8 DFA states.

Accepted Answer

The NFA exploits nondeterminism to guess. It stays in the start state reading any symbols, and at some point guesses that the current a is the third from the end, moving to a chain of three further states that consume exactly two more symbols before accepting.

That needs the start state plus three chain states, so 4 states. Correctness follows because the NFA accepts if any guess is right, and exactly one guess is right for any accepted string.

A DFA cannot guess. Reading left to right, it does not know when the end will come, so at every point it must retain enough information to answer the question once the input stops. That information is precisely the last three symbols read, since the third from the end is determined by them once no more input arrives.

There are 2 to the 3 = 8 possible values of the last three symbols, so at least 8 states are needed. That eight are also sufficient is immediate: the state is the last three symbols, updated by shifting.

To prove 8 is a genuine lower bound, take the eight strings of length 3. Any two distinct ones differ in some position. Appending a suffix of the right length moves that differing position to third-from-last, so exactly one of the two extended strings is accepted. All eight are therefore pairwise distinguishable and by Myhill-Nerode the minimal DFA has at least 8 states.

Generalising to the k-th symbol from the end gives k plus 1 NFA states against 2 to the k DFA states, which is the standard witness that the subset construction's exponential bound is tight.

Question 7

Use the Myhill-Nerode theorem to prove that the language of strings over {a, b} with an equal number of as and bs is not regular.

Accepted Answer

Consider the infinite family of strings a to the 0, a to the 1, a to the 2 and so on — that is, the strings consisting only of as.

Take any two distinct members, a to the i and a to the j with i not equal to j.

Append the suffix b to the i.

The first extended string is a to the i followed by b to the i, which has i as and i bs, so it is in the language.

The second is a to the j followed by b to the i, which has j as and i bs. Since j is not equal to i, the counts differ and it is not in the language.

So the suffix b to the i distinguishes the pair, and this construction works for every distinct pair drawn from the family.

The strings a to the 0, a to the 1, a to the 2 and so on are therefore pairwise inequivalent under the Myhill-Nerode relation, which means the relation has infinitely many equivalence classes.

The theorem states that a language is regular exactly when the number of classes is finite. This language has infinitely many classes, so it is not regular.

The intuition matches the formal argument. Recognising the language requires tracking the difference between the counts of as and bs, which is an unbounded integer, and a finite automaton has only finitely many states in which to store it.

Note that the proof took four steps and required no case analysis. The pumping lemma would need a pumping length, a witness string, and reasoning over every valid decomposition, which is why Myhill-Nerode is usually the cleaner instrument.

Question 8

Given DFAs for languages L1 with 3 states and L2 with 4 states, describe how to construct a DFA for L1 minus L2 and give an upper bound on its state count.

Accepted Answer

The difference L1 minus L2 is the set of strings in L1 but not in L2, which equals the intersection of L1 with the complement of L2.

Both operations are available. Complementing a DFA swaps its accepting and non-accepting states, which requires no new states and is valid because a DFA has exactly one computation path per string. The complement of L2 therefore has the same 4 states.

Intersection uses the product construction. The state set is the Cartesian product of the two state sets, and a transition on a symbol advances both components independently. So the product has 3 times 4 = 12 states.

The accepting set is what encodes the operation. For the difference, a product state accepts when the first component is accepting in the L1 machine and the second component is accepting in the complemented L2 machine — equivalently, when the first accepts and the second does not accept in the original L2 machine.

So the upper bound is 12 states.

Two remarks. The bound is an upper bound, not the exact count: unreachable product states may exist and equivalent ones may merge, so minimisation can reduce it. And the same 12-state product serves union and intersection too, with only the accepting set changing — both components accepting for intersection, either accepting for union — which is why the product construction is presented once and reused.

The construction also shows why complementation must precede the product rather than being applied afterwards: complementing the product would give the complement of the intersection, not the intersection with a complement.

Question 9

Determine whether (a star b star) star equals (a plus b) star, and whether (ab) star equals a star b star. Justify each answer.

Accepted Answer

First claim: (a star b star) star equals (a plus b) star. This is true.

For the forward inclusion, anything generated by the left side is a string of as and bs, so it lies in (a plus b) star, which contains every string over the alphabet.

For the reverse, take any string w over {a, b}. Each individual symbol is either an a, which lies in a star b star by taking one a and zero bs, or a b, which lies in it by taking zero as and one b. Concatenating those single-symbol pieces under the outer star reconstructs w. So every string over the alphabet is generated.

Both inclusions hold, so the two expressions denote the same language, namely all strings over {a, b}.

Second claim: (ab) star equals a star b star. This is false.

The left side generates exactly the strings formed by repeating the block ab, giving the empty string, ab, abab, ababab and so on. Every such string alternates strictly.

The right side generates any number of as followed by any number of bs, giving the empty string, a, b, aab, aaabb and so on.

The string abab is in the left language and not the right, since the right requires all as to precede all bs and abab has a b before its second a.

Conversely the string aab is in the right language and not the left, since the left produces only strings of even length alternating a and b.

Neither language contains the other, so the two are incomparable rather than merely unequal. The general lesson is that a star distributes over a repeated block quite differently from how it distributes over separate symbols, which is why the first identity holds and the second fails.

Practice — "Regular Expressions & Finite Automata"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities