September 22 * Example of the conceptual power of nondeterminism Let L be a language. Define 1/2(L) to be {x: for some y such that |x| = |y|, xy is in L}. 1/2(L) is the set of first halves of strings in L. Prove that for each regular L, 1/2(L) is regular. Proof: Let M be a DFA for L. M' will be an NFA constructed to accept 1/2(L). M' uses the "finger method" as follows. M' places the left finger on s in M, and the right finger on s_i in M where s_i is a nondeterministic "guess" as to where input x will lead. As aharacters of x are read, M' moves the left finger along transitions as dictated by characters read, and simultaneously moves the right finger along a nondeterministically chosen edge (which may be labeled with any character, not necessarily the one of x being read). M' accepts x iff at the end its left finger is on s_i and its right finger is on the accept state. Thus M' accepts x iff * x leads to some state s_i in M, and * there exists y |y| = |x| s.t. y leads from s_i to an accept state in M. Formally: Use tuple for fingers (we need a middle finger to remember the guessed s_i state). M' = (K', Sigma, delta', s', F'), where K' = K_{left finger} x K{middle finger} x K{right finger} and s in K = new start state * delta'(s, epsilon) = {: si in S} "Guess" the state si to which input x will lead * delta'( , a) = { : delta(si, a) = sl and there exists b in Sigma s.t. delta(sk, b) = sm} Note that the middle finger does not change after the initial guess F' = { : si in S, sj in F} As you can see, the left finger moved on input x to where the middle finger guessed (si, si). The right finger moved from si to some accepting state sj of M (si, sj). * RE -> NFAs with epsilon-transitions Theorem: Forall regular expressions r, construct NFA M L(M) = L(r). Proof: By induction on the number of operations in r we show there exists an NFA with one final state for L(r). Base Case: Number of operations = 0. r is either +-+ +===+ empty, so NFA is ->| | || || +-+ +===+ +===+ epsilon, so NFA is ->|| || +===+ +-+ a +===+ a in Sigma, so NFA is ->| |-->|| || +-+ +===+ Inductive Hypothesis: Assume property holds for r defined with <=n operations. Inductive Step: Prove property then holds for r = n+1 operations. In this case there exist r1, r2 defined using <=n operations each such that r is one of (r1r2), (r1 v r2), or (r1*). Let M1, M2 be NFAs with one final state accepting r1 and r2 respectively (by inductive hypothesis M1 and M2 exist). Your homework assignment will be used to complete the inductive step. * DFA -> RE Theorem: Given a DFA M = (K, Sigma, delta, s1, F), construct a regular expression r for L(M). Proof: Let R_{i j}^{k} = strings leading from si to sj that do not pass through any states numbered > k (although they may begin or end at one). Assume K = {s1, ..., sn}. Then R_{ij}^{n} = strings leading from si to sj and if F = {sj_1, sj_2, ..., sj_s} then L(M) = R_{1 j1}^{n} union R_{1 j2}^{n} union ... union R_{1 js}^{n}. L(M) = all ways to get to final states with paths that do not pass through any states numbered higher than n. Lemma. Forall i, j, k there exists regular expression r_{ij}^{k} s.t. L(r_{ij}^k) = R_{ij}^k The theorem follows from the lemma. L(M) = R_{1 j1}^n union R_{1 j2}^n union ... union R_{1 js}^n = L(r_{1 j1}^n) union ... union L(r_{1 js}^n) = L(r_{1 j1}^n v r_{1 j2}^n v ... v r_{1 js}^n), which is a regular expression for L(M) Now we will proof the lemma. Note that +----- +--- | R_{ij}^0 = | a: delta(s_i, a) = s_j if i neq j | | a: delta(s_i, a) = s_j union e if i = j | +--- | R_{ij}^k = R_{ij}^k-1 union R_{ik}^k-1(R_{kk}^k-1)*R_{kj}^k-1 +----- How do we transition from i to j without going through states higher than k? Either by transitioning from i to j without going through states higher than k-1, or by transitioning from i to k without going through states higher than k-1 followed by transitioning from k to k in one move without going through states higher than k-1 followed by transitioning from k to j without going through states higher than k-1. +------------------------------------+ | | | |<- States > k | | +----------------S_k-----------------+<- States = k | ^| ^^ | S_1----->O==========++-+| |<- States < k | | | | v |---> means one move | +======O |===> means a finite sequence of moves +------------|-----------------------+ v S_j We will prove the lemma by induction on k using the note. Base Case: Let k = 0. By the first part of the note, R_{ij}^0 <= Sigma union e and thus there exists a simple regular expression for the finite set (the union of individual symbols and/or e) Inductive Hypothesis: Assume forall i, j that r_{ij}^k-1 is a regular expression for R_{ij}^k-1. Inductive Step: Prove that there exists re for R_{ij}^k. By the second part of the note, R_{ij}^k = R_{ij}^k-1 union R_{ik}^k-1(R_{kk}^k-1)*R_{kj}^k-1 = L(r_{ij}^k-1) union L(r_{ik}^k-1)(L(r_{kk}^k-1))*L(r_{kj}^k-1) = L(r_{ij}^k-1 v r_{ik}^k-1(r{kk}^k-1)*r_{kj}^k-1). Because each of the rs are re, the entire equation is a re. * Example 1 1 +--+ +----+ v | 0 v | +--+----------->+====+ |s1| 0 ||s2|| +--+<-----------+====+ L(M) = L(r_{12}^2) r_{12}^2 = r_{12}^1 v r_{12}^1(r_{22}^1)*r_{22}^1 = r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0 v r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0(r_{22}^1)*r_{22}^1 = r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0 v r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0 (r_{22}^0 + r_{21}^0(r_{11}^0)*r_{12}^0)+ We know that r_{11}^0 = r_{22}^0 = 1 v e r_{12}^0 = r_{21}^0 = 0 = 0 v (1 v e)+0 v (0 v (1 v e)+0)[(1 v e) v 0(1 v e)*0]+ = (0 v (1 v e)+ 0)[1 v e v 0(1 v e)*0]+ = (0 v (1 v e)+ 0)[1 v e v 01*0]* = (1 v e)*0(1 v e v 01*0)* = 1*0(1 v 01*0)*