Examples of NFA Constructions
These exercises are taken from Introduction to the Theory of Computation by Michael Sipser.
Example 1
Let A be a regular language over an alphabet Σ. Define DROP-OUT(A) to be the language consisting of all strings that can be obtained by removing one symbol from a sting in A. Explicitly,
DROP-OUT(A) = {xz | xyz ∈ A,x,z ∈ Σ∗,y ∈ Σ}. Show that DROP-OUT(A) is regular.
Let M = (Q, Σ, δ, q0, F) be a DFA recognizing A, we create an NFA M′ that recog- nizes DROP-OUT(A). Pictorially, we have two copies of M and we add an ε-transition from every state in the first copy to the states in the second copy that are normally attainable.Moreformally,wehaveM′ =(Q×{0,1},Σ,δ′,(q0,0),F×{1})withδ′ defined as follows.
For all q ∈ Q, s ∈ Σ,
δ′((q,0),s) = {(δ(q,s),0)}∪{(r,1) | ∃s′ ∈ Σ,δ(δ(q,s),s′) = r}
δ′ ((q, 1), s) = {(δ(q, s), 1)}.
Briefly, this machine simulates the DFA on the input and non-deterministically chooses to read a symbol that is not there at some point in the computation. When it does that, it moves to the second copy of the machine where it has no ε-transitions, so it must read the rest of the input normally. Note that the non-determinism is really important here as the machine can simulate any missing letter it wants at any time (although only once during the computation).
We now have to formally prove that this M′ recognizes DROP-OUT(A).
If w ∈ DROP-OUT(A), we can write it as xz where x, z ∈ Σ∗ and there exists y ∈ Σ such that xyz ∈ A. Therefore, there is a branch of computation of M′ that reads the whole string x without taking any ε-transition and then takes the ε-transition corresponding to reading y before reading the whole string z in the second copy. After all this computation, M′ is in the same state as M after reading xyz so it accepts w.
If M′ accepts w, then M′ is in the second copy of the DFA, so it must have taken an ε-transition, say it corresponds to reading the symbol y ∈ Σ. We can look at the branch of computation that accepts to write w as xz where x was read in the first copy and z was read in the second copy. We conclude that M accepts xyz, so w ∈ DROP-OUT(A).
This finishes the proof that DROP-OUT(A) is regular as it is recognized by an NFA.
1
Example 21
Let B and C be regular languages over Σ = {0, 1}. Define
B←1 C={w∈B|∃y∈C,wandycontainequalnumbersof1s}.
Show that this language is regular. We also define
ONE(C)={w∈Σ∗ |∃y∈C, wandyhavethesamenumberof1s}.
If we show that ONE(C) is regular, then it will imply B ←1 C is regular because
B ←1 C = ONE(C) ∩ B and the class of regular languages is closed under intersection2. Let M = (Q, Σ, δ, q0, F) be a DFA that recognizes C, we will construct an NFA M′ that recognizes ONE(C). The idea is that M′ will simulate M without taking into account the 0’s of the input and bypassing the 0 transitions in M. This will recognize ONE(C) because we only care about the 1s in this language. Formally, we have M′ =
(Q, Σ, δ′, q0, F), where δ′ is defined as follows3: For all q ∈ Q,
δ′(q,1) = {δ(q,1)}∪{r ∈ Q | ∃k ∈ N,δ∗(δ(q,1),0k)} δ′(q, 0) = {q}
If w ∈ ONE(C), then there exists y ∈ C with the same number of 1’s and on input w, there is a branch of computation of M′ that does the exact same changes of states as M on y (except maybe some transition from a state to itself when reading a 0), hence this branch accepts w.
If M′ accepts w, we will transform w to a word w′ in C without adding any 1’s. Consider the accepting branch of computation, for each transition arrow taken that was not in M, do the following: if the arrow is a ε-transition, add a 0 to w in this place, otherwise, if it was a 0-transition, remove the 0 that was consumed for the transition. After these transformations, w′ will be accepted by M, so w ∈ ONE(C).
This finishes the proof that ONE(C) is regular.
1The book contains an alternate solution.
2This will probably be proven in class, otherwise, a proof can easily be found online.
3δ∗ denotes the the transition function extended to Σ∗ in the usual way, i.e.: δ∗(q, aw) = δ∗(δ(q, a), w)
foranyq∈Q,w∈Σ∗ anda∈Σ.
2