This document discusses proving that the language half(L) is regular for any regular language L. It defines half(L) as the set of first halves of strings in L. The document then presents an example of constructing a deterministic finite automaton (DFA) M' that accepts half(L). M' tracks the set of states S_n from which the original DFA M for L can reach an accepting state in n transitions. The document proves that this construction shows half(L) is regular. It also discusses constructing a nondeterministic finite automaton (NFA) for half(L) using a similar approach.
This document discusses proving that the language half(L) is regular for any regular language L. It defines half(L) as the set of first halves of strings in L. The document then presents an example of constructing a deterministic finite automaton (DFA) M' that accepts half(L). M' tracks the set of states S_n from which the original DFA M for L can reach an accepting state in n transitions. The document proves that this construction shows half(L) is regular. It also discusses constructing a nondeterministic finite automaton (NFA) for half(L) using a similar approach.
This document discusses proving that the language half(L) is regular for any regular language L. It defines half(L) as the set of first halves of strings in L. The document then presents an example of constructing a deterministic finite automaton (DFA) M' that accepts half(L). M' tracks the set of states S_n from which the original DFA M for L can reach an accepting state in n transitions. The document proves that this construction shows half(L) is regular. It also discusses constructing a nondeterministic finite automaton (NFA) for half(L) using a similar approach.
This document discusses proving that the language half(L) is regular for any regular language L. It defines half(L) as the set of first halves of strings in L. The document then presents an example of constructing a deterministic finite automaton (DFA) M' that accepts half(L). M' tracks the set of states S_n from which the original DFA M for L can reach an accepting state in n transitions. The document proves that this construction shows half(L) is regular. It also discusses constructing a nondeterministic finite automaton (NFA) for half(L) using a similar approach.
Winter, 2011 Proving regularity of languages, an example: half(L) Various operations can be performed on regular languages to yield other languages. The languages obtained thus may or may not be regular. Assignment #3 will ask you to example several such operations. As an illustration of some of the techniques one uses to solve such problems, we will solve one of the exercises from the textbook. Problem 1. Let L be a language. Dene half(L) to be {x | for some y such that |x| = |y|, xy is in L} . That is, half(L) is the set of rst halves of strings in L. Prove that for each regular language L, half(L) is regular. Suppose we are told that L is regular. What useful information does this give us? Well, we know that there is a DFA that accepts L. Also, there is a regular expression that represents L. We could use any of these facts in proving that half(L) is regular. Let M be the DFA accepting L. Let q 0 be the start state and F the set of nal states of M. Now consider a string x. How do we check if x belongs to half(L)? We have to check if there is a string y of the same length as x which when concatenated with x gives a string in L, i.e., the automaton moves to a nal state on input xy. Suppose M goes to state q i on seeing input x, i.e., (q 0 , x) = q i . We must check if there is a string y, |y| = |x|, such that y takes the DFA from q i to a nal state, i.e., (q i , y) F. Suppose we have seen n symbols so far, i.e., |x| = n. Let S n be the set of all states that lead to a nal state on some input of length n. If q i S n , then x half(L) and vice versa. (Prove this!) Thus if we can keep track of S n and q i , we can determine if x half(L). Note that S 0 is just F. We can obtain S n+1 from S n and . Let T be the set of all states that have some transition (on a single symbol) to a state in S n . We claim that S n+1 = T. Indeed, if for each state q S n there is some input of length n that takes M from q to a nal state, then for each state q
T there is some input of length n + 1 that takes M from q
to a nal state. Further, if S n contains all states from where a nal state can be reached in n transitions, T contains all states from where a nal state can be reached in n+1 transitions. Thus T = S n+1 . How to we keep track of and update S n ? We construct a DFA M
that stores this
information in its state. Let Q be the set of states of M. The states of M
are elements of Q 2 Q . Each state of M
is a pair consisting of a single state of M, and a set of states of M. Let
be the transition function for M
. We construct M
such that if an input x of length n takes M to
state q i , x takes M
to the state (q i , S n ) where S n is the set of states dened above. 1 Formally we dene S S Q , prev(S) = {q Q| a , q
S, (q, a) = q
} Note that S n+1 = prev(S n ). We dene the transition function
as follows:
(q, S), a
(q, a), prev(S)
The start state is q
0 = (q 0 , S 0 ), i.e., (q 0 , F). The set of nal states is F
= {(q, S) | q Q, S 2 Q , q S}. Now we can prove by induction that
(q
0 , x) =
(q 0 , x), S n
, where |x| = n. By denition
of the set of nal states, x is accepted i (q 0 , x) S n . Thus M
accepts the language half(L).
Thus we have constructed a DFA that accepts half(L). This proves that half(L) is regular. As an exercise, complete the inductive proofs we need to prove the correctness of this construction. Note: In general, to show that two languages L 1 and L 2 are equal, we must prove that every string in L 1 belongs to L 2 and every string in L 2 belongs to L 1 . This is establishes that L 1 L 2 and L 2 L 1 , proving that L 1 = L 2 . In proving the correctness of the above construction, we have to prove something similar to show that L(M
) = half(L). Consider x
such that
(q
0 , x) =
(q 0 , x), S n
where |x| = n. Then we must prove
that x half(L) q
0 S n and q
0 S n x half(L). We mentioned these facts in the above discussion, but did not prove them. They can be proved from the denition of half(L) and S n . This technique for proving equality of languages also applies to proving equivalence of regular expressions or proving that a regular expression corresponds exactly to the set dened by an informal English language description. For example, given an English description of a language, to prove the correctness of a regular expression, we must prove that every string generated by the regular expression ts the English language description, and further, every string that ts the English language description can be generated by the regular expression. We can also construct an NFA M
for half(L), the states of which are elements of Q
Q
{q
0 }. The idea behind this construction is similar to the idea that the DFA construction was based upon. Here, if an input x, |x| = n, takes M to state q i , x takes M
to all states of the form (q i , q), where q is a state from which a nal state can be reached in n transitions, i.e., q S n . Note that the rst component q i is the same as the rst component in the state for the DFA M
. However for the second component, in place of the set of states S
n , the NFA guesses an element of S n . The start state of M
is a new state q
0 . q
0 has transitions to all states of the form (q 0 , q) where q F. The nal states are the states of the form (q, q). To dene the transition function of M
, we rst dene the function prev on states of M:
p Q, prev(p) = {q Q| a , (q, a) = p} . 2 The transition function
of M
dened as follows:
(q, p), a
= {
(q, a), p
| p
prev(p)} . Do you see the connection between this construction and the one given previously? As an exercise, prove that L(M
) = half(L). Your proof should be similar to the proof of the
