Monday, June 27, 2011

Sipser 2.43: DROPOUT(A)

Let A be any language. DROPOUT(A) is defined as the language containing all strings that can be obtained by dropping one symbol from a string in A. We have to show that the class of regular languages is closed under the DROPOUT operation.
DROPOUT(A) = {xz | xyz ∈ A, where x,z ∈ Σ*, y ∈ Σ}

This means that given a DFA for A, we have to construct a DFA/NFA for DROPOUT(A).  This looks like a good opportunity to introduce ε-transitions. Let [A]1[B] represent a transition from state A to state B on a 1. If we replace this with [A]ε[B], then if we ever reach state A, we go directly to state B without reading any input. In effect we will have dropped the 1.

But the symbol to drop can occur at any position in the string. So I thought I will make a copy of the given DFA for each state it contains. In that copy, I will put ε on all arrows going out of that state. Then a union of all these copies would be the required NFA. However I think there is a problem with this idea. If the state occurs in a loop, then it would be possible to drop 2 or more symbols and still end up at the accept state.

1 comment:

  1. Wynn Las Vegas - MapyRO
    Wynn 의왕 출장샵 Tower Suite King · 2 King Beds · Bathtub · 2 Double 남원 출장안마 Bedroom Sauna · Two 충주 출장마사지 Double 오산 출장마사지 Baths · King Resort King · Wynn Tower Suite King · 계룡 출장안마 Wynn Tower Suites

    ReplyDelete