CSE355_SP24_mid1sol

CSE 355 Page 2 M idterm 1 - S ample S olutions Question 1-5: Determine whether the given statement is True or False. If it is true, give a brief reasoning as to why, otherwise give a counter-example . ALL of the points are for the reasoning; each is worth 2 points 1. (T / F) If R is a regular expression, ( RR ⇤ [ R ) ⇤ R = R + TRUE : RR ⇤ is R + , then RR ⇤ [ R = R + because R ⇢ R + . Then, it follows that ( R + ) ⇤ is R ⇤ . Finally, R ⇤ R evaluates to R + . Common mistake is just saying ( RR ⇤ [ R ) evaluates to R without explaining. 2. (T / F) A subset of a regular language is regular. FALSE : Every nonregular language is a subset of the regular language ⌃ ⇤ . 3. (T / F) Let L 1 = L 2 L 3 . If L 2 is regular and L 3 is not regular, L 1 is never regular. FALSE : Let L 2 = L (1 ⇤ ) and it is surely regular. Let L 3 = { 1 n | n is a prime number } , which is not regular (proved in the problem set for PL). The concatenation of L 2 and L 3 is L 1 = L (111 ⇤ ). It is surely regular because it is expressed in a regular expression. 4. (T / F) L 1 is an infinite regular language. Every DFA M where L ( M ) = L 1 , contains at least one cycle in its state diagram. TRUE : If L 1 is infinite regular language and M is a DFA that recognizes L 1 , there always is a string w 2 L 1 , where | w | > = | Q | , ( Q is the finite set of states in M ), otherwise L 1 is finite. In the accepted computation of w on M , there must be exactly | w | many transitions ( | w | + 1 states are visited) or at least as many transitions as | Q | . By pigeon hole principle, there must be at least one state that is visited multiple times, there must be a cycle in M . Common mistake is just mentioning infinite language must go through loop. Pigeon hole principle must be used to compare the length of string and the numbber of states to receive credit. 5. (T / F) The intersection of a nonregular language and a regular language cannot be regular. FALSE : The intersection of every nonregular language and the regular language ; is ; . 2 Copyright c 2024 Heewook Lee

CSE 355 Page 3 M idterm 1 - S ample S olutions Q5-10 : Determine whether the given statement is True or False. Write ‘T’ if true, ‘F’ otherwise. 6. If you used the method shown in lecture to convert (01 [ 10) ⇤ into an equivalent NFA, how many total states and accept states would the machine have? [ C ] (a) 8 total states, 5 accept states (b) 6 total states, 3 accept states (c) 10 total states, 3 accept states (d) 9 total states, 5 accept states (e) None of the above 7. Let L = { www | w 2 { 0 , 1 } ⇤ } . Which of the following is true? [ C ] (a) L is nonregular because 0 p 10 p cannot be pumped. (b) L is regular because the regular expression ⌃ ⇤ ⌃ ⇤ ⌃ ⇤ describes the language. (c) L is nonregular because 0 p 10 p 10 p 1 cannot be pumped. (d) L is regular because a finite automaton can be built to recognize it. (e) Both (a) and (c) 8. If L 1 = { a n | n ≥ 0 } and L 2 = { b n | n ≥ 0 } , consider I. L 1 · L 2 is regular language. II. L 1 · L 2 = { a n b n | n ≥ 0 } Which one of the following is correct? [ A ] (a) Only I (b) Only II (c) Both I and II (d) Neither I nor II 9. To show that a language is regular, one could give a DFA for it. One could also [ D ] (a) give a regular expression. (b) use the pumping lemma for regular languages. (c) use closure properties. (d) (a) or (c) (e) (a), (b), or (c) 10. L = { ( ab ) n : n ≥ 0 } [ E ] (a) not regular because you cannot remember n . (b) not regular because ( ab ) p cannot be pumped. (c) not regular because ( ab ) p cannot be pumped. (d) regular because it is a ⇤ b ⇤ . (e) regular because it is ( ab ) ⇤ . 3 Copyright c 2024 Heewook Lee

CSE 355 Page 5 M idterm 1 - S ample S olutions The state diagram of M 3 is provided again for your convenience. q 0 q 1 q 2 0 0 1 1 0 1 (d) Use the GNFA method discussed in lecture to convert the DFA from part (b) to a regular expression R (show all your work). NOTE : Must use the ripping order of q 1 , q 0 , q 2 to receive any credit ( 15 points ). Step 1: convert the DFA to GNFA. 1pt for correct GNFA conversion q s q 0 q 1 q 2 q a " 0 0 1 1 0 1 " Step 2: Rip q 1 . 3pt for each path restoration (6pts), error results in deduction q s q 0 q 2 q a " 0 0 11 ⇤ 0 11 ⇤ 0 " Step 3: Rip q 0 . 3pt for each path restoration (6pts), error results in deduction q s q 2 q a 0 ⇤ 11 ⇤ 0 00 ⇤ 11 ⇤ 0 [ 11 ⇤ 0 " Step 4: Rip q 2 . 3pt for the last path restoration, error results in deduction q s q a 0 ⇤ 11 ⇤ 0(00 ⇤ 11 ⇤ 0 [ 11 ⇤ 0) ⇤ 5 Copyright c 2024 Heewook Lee

CSE 355 Page 6 M idterm 1 - S ample S olutions Question L-2: ( 15 points total ) For the following NFA, use the power-set construction (add states only as needed) to obtain an equivalent DFA. Provide its state diagram. q 0 q 1 q 3 q 2 q 4 0 , 1 " 1 0 0 1 0 1 " 0 { q 0 , q 1 } { q 0 , q 1 , q 2 , q 3 } { q 0 , q 1 , q 2 } { q 0 , q 1 , q 2 , q 3 , q 4 } 0 1 1 0 1 0 0 1 2pt for correct start state 2pt for correct final state 3pt for having correct number of states 8pt for overall structure (-1 for each error) 6 Copyright c 2024 Heewook Lee

CSE 355 Page 8 M idterm 1 - S ample S olutions Question L-4: If a language L is regular, show that the following language is also regular: ShoveHash ( L ) = { x # y | xy 2 L : x , y 2 ⌃ ⇤ } , Example: if L = { ✏ , 0101 } , then ShoveHash ( L ) = { # , #0101 , 0#101 , 01#01 , 010#1 , 0101# } . Note: Use the proof by construction technique and explain your idea before writing out the proof ( 20 points ). If we have an ability to accept x · y 2 L , how can we modify the machine that recognizes L in such a way that the new machine accepts x # y ? Also, it’s important to remember that # must be a part the input (the machine doesn’t just randomly shove #’s. After all, finite state machines are recognizers). Remember that the machine can only read and say “accept” or “reject” at the end of input. The core idea to solve this problem is that in the new machine that we are running to accept ShoveHash ( L ) needs two copies of the original machine where you can jump from a state q in the first machine to the corresponding state q 0 in the second machine by reading an 1. But this step must be done nondetermincally so we can accept any variant of string with an insertion of ‘#’ at any position. Here is a complete construction: Since L is regular, there must be a DFA M 1 = ( Q 1 , ⌃ 0 , δ 1 , q 1 , F 1 ) that recognizes L . Let M 2 = ( Q 2 , ⌃ 0 , δ 2 , q 0 1 , F 2 ) be an identical copy of M 1 with di ↵ erent labels. If q i 2 Q 1 , we denote q 0 i 2 Q 2 to be the corresponding state of q i in M 2 . In order to recognize ShoveHash( L ) , we construct a new NFA N = ( Q N , ⌃ , δ N , { q 1 } , F N ), where 1. Q N = Q 1 [ Q 2 , 2. ⌃ = ⌃ 0 [ { # } 3. δ ( q , a 2 ⌃ ) = 8 > > > > > < > > > > > : { δ 1 ( q , a ) } q 2 Q 1 and a , # , { δ 1 ( q , a ) , q 0 } q 2 Q 1 and a = # ( q 0 is the corresponding state of q ) { δ 2 ( q , a ) } q 2 Q 2 , 4. { q 1 } , 5. F N = { q | q 2 F 2 } . 8pt for explaining a correct idea (Make sure ‘#’ is a part of input) 12pt for formal writeup of the idea - 2pt for setting up machine definition for both machines - 2pt for explaining a notation for corresponding states - 5pt for correctly defining the transition function - 1pt for correctly defining states - 1pt for correctly defining accept states - 1pt for correctly defining the start state (Note) can only get 10pt max if they assume ⌃ of L already contains # Common error is using only one copy of machine which cannot ensure that only one # is inserted. 8 Copyright c 2024 Heewook Lee