Question

Problem 3.3: For a string x € {0,1}*, let af denote the string obtained by changing all 0's to l's and all l's to O's in x. Given a language L over the alphabet {0,1}, define FLIP-SUBSTR(L) = {uvFw: Uvw E L, U, V, w € {0, 1}*}. Prove that if L is regular, then FLIP-SUBSTR(L) is regular. (For example, (1011)F = 0100. If 1011011 e L, then 1000111 = 10(110) F11 € FLIP-SUBSTR(L). For another example, FLIP-SUBSTR(0*1*) = 0*1*0*1*.) (Hint: given an NFA (or DFA) for L, construct an NFA for FLIP-SUBSTR(L). Give a formal description of your construction. Provide an explanation of how your NFA works, including the meaning of each state. A formal proof of correctness is not required.] Bonus ( points?): Consider the modified language FLIP-SUBSTR(L) = {uumw: Uvw EL, u, v, we {0,1}*}, were vR denotes the reverse of v. Prove that if L is regular, then FLIP-SUBSTR(L) is regular.

Answer 1

Answer: We can say that a language is regular or not by checking are we able to create a DFA or NFA for the given language or not. In these question i am showing we can create a NFA for the above alternations of flip-substring and flip-reverse by adding some lamda transaction in the sequence which is accepting our string. As for infinite languages we can create infinite sequence of states from starting state hence it is possible to alter all the states as our particular need. Hence we can say that they are also regular because a NFA (Finite Automata) exists which accepts all those string.

33 Flip-Substr(L) = { ust w w w EL, u, v, we long To prove: Flip- Substr (L) is regular First i like to show some intuition DEA and NFA. of *0=ار80ممم DEA no NFA ر عد) عمل (infinite) given Now, we took question an example in لب همه 1=L || 15 15 - (ا ) Subs- والا OFA for L: 00000000 IDEA for Flip -subsh (L) © جلیلی این عینی We just flipped the transaction in DEA /NEA

Now it is given that L is regular language then we create a DEA Or NFA for it. For Flip-Substo (2) we need to flip the transaction between the nodes of NFA which results in a NFA for flip. hence, Flip-substo (2) is also regular Bonus : Flip -substs (L) - Luv w nowel, 4.0, we hold For Reversal of a substring we need to - add a lamda (2) transaction in our NEA. example :- to 10 (001il F(L) =_1041004 NEA For L: Same in the previous page NFA for F (L): +0 -0 oooooo which can further be solved by adding a state... -osoro o 0:00 Oloto - Adding reverse the direction in NFA A rneta