Homework #4 1. Construct a DFA equivalent to the NFA defined by ({p,q,r,s}, {0,1}, delta, p, {s}), where delta is defined by the chart below. | 0 1 -+-------- p|p,q p q| r r r| s - s| s s Solution: The equivalent DFA is defined by ({{},p,q,r,s,pq,pr,ps,qr,qs,rs,pqr,pqs,prs,qrs,pqrs}, {0,1}, delta', p, {s,ps,qs,rs,pqs,prs,qrs,pqrs}), where delta' is defined by the chart below. | 0 1 ----+--------- {}| {} {} p| pq p q| r r r| s {} s| s s pq| pqr pr pr| pqs p ps| pqs ps qr| rs r qs| rs rs rs| s s pqr|pqrs pr prs| pqs ps qrs| rs rs pqrs|pqrs prs 2. Construct a finite automata equivalent to the regular expression (1 v 01 v 001)* (e v 0 v 00). Solution: e +--------------------------------------------+ | | | e +-+ 1 +-+ e | | +----->| |--->| |--------------------+ | v / +-+ +-+ v | +-+ e +-+ 0 +-+ 1 +-+ e +-+---+e +-+ --->| |------->| |--->| |--->| |----------->| |----->| |-----+ +-+ +-+ +-+ +-+ +-+ +-+ | | \ e +-+ 0 +-+ 0 +-+ 1 +-+ e ^ ^ | | +----->| |--->| |--->| |--->| |------+ | | | +-+ +-+ +-+ +-+ | | | e | | +------------------------------------------------+ | | +-------------------------------------------------------------+ | | e +-+ e +-+ e | +----->| |--->| |-----------+ | / +-+ +-+ v | +-+ e +-+ 0 +-+ e +===+ +--->| |------->| |--->| |-------->|| || +-+ +-+ +-+ +===+ \ e +-+ 0 +-+ 0 +-+ e ^ +----->| |--->| |--->| |----+ +-+ +-+ +-+ 3. Construct a regular expression for the state diagram shown below. 0 1 +---+ +-+ | | | | v | v | +===+ 1 +-+ -->||A||------->|B| +===+ +-+ ^ | ^ | 0 | | 1 | v | | 0 +-+ +----------|C| +-+ Solution: Let A = state 1, B = state 2, C = state 3. Then L(M) = R_{11}^3. R_{11}^3 = R_{11}^2 v R_{13}^2(R_{33}^2)*R_{31})^2 R_{11}^2 = R_{11}^1 v R_{12}^1 (R_{22}^1)* R_{21}^1 R_{11}^1 = R_{11}^0 v R_{11}^0 (R_{11}^0)* R_{11}^0 = (0 v e) v ((0 v e) (0 v e)* (0 v e)) R_{12}^1 = R_{12}^0 v R_{11}^0 (R_{11}^0)* R_{12}^0 = 1 v (0 v e)(0 v e)*1 R_{22}^1 = R_{22}^0 v R_{21}^0 (R_{11}^0)* R_{12}^0 = (1 v e) R_{21}^1 = R_{21}^0 v R_{21}^0 (R_{11}^0)* R_{11}^0 = empty R_{11}^2 = (0 v e) v ((0 v e) (0 v e)* (0 v e)) R_{13}^2 = R_{13}^1 v R_{12}^1 (R_{22}^1)* R_{23}^1 R_{13}^1 = R_{13}^0 v R_{11}^0 (R_{11}^0)* R_{13}^0 = empty R_{23}^1 = R_{23}^0 v R_{21}^0 (R_{11}^0)* R_{13}^0 = 0 R_{13}^2 = (1 v (0 v e)(0 v e)*1)(1 v e)* 0 R_{33}^2 = R_{33}^1 v R_{32}^1 (R_{22}^1)* R_{23}^1 R_{33}^1 = R_{33}^0 v R_{31}^0 (R_{11}^0)* R_{13}^0 = e R_{32}^1 = R_{32}^0 v R_{31}^0 (R_{11}^0)* R_{12}^0 = 1 v 0(0 v e)* 1 R_{33}^2 = e v (1 v 0(0 v e)*1)(1 v e)*0 R_{31}^2 = R_{31}^1 v R_{32}^1 (R_{22}^1)* R_{21}^1 R_{31}^1 = R_{31}^0 v R_{31}^0(R_{11}^0)*R_{11}^0 = 0 v 0(0 v e)*(0 v e) R_{31}^2 = 0 v 0(0 v e)*(0 v e) R_{11}^3 = [(0 v e) v ((0 v e) (0 v e)* (0 v e))] v [((1 v (0 v e)(0 v e)*1)(1 v e)* 0) (e v (1 v 0(0 v e)*1)(1 v e)*0)* (0 v 0(0 v e)*(0 v e))] = 0* v [0*1 v 0(0*1+0)*0*] 4. Which of the following languages are regular sets? Prove your answer. a) L1 = {0^{2n} | n >= 1} b) L2 = {0^p 1^q 0^{p+q} | m >= 1 and n >= 1} c) L3 = {x x^R: x in (0 v 1)+} d) L4 = The set of all strings in (0 v 1)+ that do not contain the substring 010. Solution: a) Regular. Here is a finite state machine that accepts the language. 0 +-----------+ | | v | +-+ 0 +-+ 0 +===+ --->| |------->| |------->|| || +-+ +-+ +===+ b) Nonregular. Assume that L2 is regular. By the pumping lemma, there is a constant n such that for any z in L2, |z| >= n, we can break z into u, v, and w such that |uv| <= n, |v| >= 1, and know that uv^iw is in L2 for all i >= 0. We pick z to be 0^n 1^n 0^{2n}. For this string, u and v will be within the first segment of 0s. Let u = 0^s and v = 0^t, where s+t <= n and t >= 1. The pumping lemma claims that 0^s 0^{i*t} 0^{n-s-t} 1^n 0^{2n} is in L2. When i = 0 this is not true because the string will be 0^{n-t} 1^n 0^{2n}, and n-t does not equal n because t >= 1. Thus the language is not regular. c) Nonregular. Assume that L3 is regular. By the pumping lemma, there is a constant n such that if z is in L3, |z| >= n, then there exists u, v, w such that |uv| <= n, |v| >= 1, z = uvw and uv^iw is in L3 for all i >= 0. Let z = 1^n 00 1^n. With this selection, both u and v are within the first segment of 1s. Let u = 1^s and v = 1^t, where s + t <= n and t >= 1. The pumping lemma claims that 1^s 1^{i*t} 1^{n-s-t} 00 1^n is in L3. This is not true: if i = 0, the resulting string is 1^{n-t} 00 1^n, which is not in the language L3. d) Regular. It is easy to generate a finite state machine that accepts the complement of L4 (all strings containing 010), as shown below. +-+ 0 +-+ 1 +-+ 0 +===+ --->| |------->| |------->| |------->|| || +-+ +-+ +-+ +===+ Because we have shown that L4 complement is regular, and we know that regular sets are closed under complementation, we then know that L4 is regular. 5. Use the pumping lemma to prove that language L defined below is not regular. L = {ww^c: w in {a,b}*}, where w^c stands for w with each occurrence of a replaced by b, and vice versa. Solution: You should be able to sense that this is nonregular, because it would be necessary to remember the first half of the string in order to be able to check whether the second half is the corresponding symbol-by-symbol complement. That would require an amount of memory linear in the size of the input string, while only a constant amount of memory is available in a DFA. Recall we showed in class that the language 0^k 1^k, k>= 0, is nonregular. The same argument can be used to show that a^k b^k is nonregular. If we generate the intersection of the language in question L with the known regular language a*b* we obtain the language a^k1^k, k>= 0. Because the resulting language is not regular and regular languages are closed under intersection, the language in question is not regular. 6. Are the following statements true or false? Explain your answer in each case. Solution: a) False. We will show this by contradiction. We know that the language L1 = 0*1* is regular. We also know that the language L2 = 0^n1^n , n>=0, is a subset of L1 because every string in L2 is in L1. However, we have proven in class that L2 is not regular, so regular languages are not closed under subset. c) True. We know that L is regular. We also know that the set of all strings not in L, the complement of L (L_c) is regular because regular languages are closed under complementation. We are then considering the concatenation of two regular languages which we have shown in class to be regular. e) True. If L is a regular language, then there exists an NFA that recognizes strings in L. We can use this NFA to construct an NFA for the language in question, L'. 7. Simulate your constructed DFA from problem 1 using the DFA simulator available at http://ranger.uta.edu/~cook/tcs/fsm/Simulator.html Turn in a picture of the constructed DFA. You will need a browser capable of running Java applets to complete this homework problem.