Homework 3Solutions - New Jersey Institute of Technology

1 CS 341: Foundations of Computer Science IIProf. Marvin NakayamaHomework 3 Solutions1. Give NFAs with the specified number of states recognizing each ofthe following lan-guages. In all cases, the alphabet is ={0,1}.(a) The language{w |wends with00}with three ,100(b) The language{w |wcontains the substring0101, ,w=x0101yforsomex, y }with five ,101010,1(c) The language{w |wcontains at least two0s, or exactly two1s}with 0,10100,11010(d) The language{ }with one (e) The language0 1 0 0with three 1002. (a) Show by giving an example that, ifMis an NFA that recognizes languageC,swapping the accept and non-accept states inMdoesn t necessarily yield a newNFA that :The NFAM below recognizes the languageC={w |wends with00},where ={0,1}.

2 1230,100 Swapping the accept and non-accept states ofMgives the following NFAM :1230,100 Note thatM accepts the string1006 C={w|wdoes not end with00}, soM does not recognize the languageC.(b) Is the class of languages recognized by NFAs closed under complement? Explainyour :The class of languages recognized by NFAs is closed under complement, which wecan prove as follows. Suppose thatCis a language recognized by some NFAM, ,C=L(M). Since every NFA has an equivalent DFA (Theorem ), thereis a DFAD such thatL(D) =L(M) =C. By problem 3 on Homework 2, wethen know there is another DFAD that recognizes the languageL(D). Since2every DFA is also an NFA, this then shows that there is an NFA, in particularD,that recognizes the languageC=L(D).

3 Thus, the class of languages recognizedby NFAs is closed under Use the construction given in Theorem to convert the following NFAN into anequivalent aaa, bbAnswer:Let NFAN= (Q, , ,1, F), whereQ={1,2,3}, ={a, b},1isthe start state,F={2}, and the transition function as in the diagram construct a DFAM= (Q , , , q 0, F )that is equivalent to NFAN, first wecompute the -closure of every subset ofQ={1,2,3}.SetR Q -closureE(R) {1}{1,2}{2}{2}{3}{3}{1,2}{1,2}{1,3}{1,2, 3}{2,3}{2,3}{1,2,3}{1,2,3}Then defineQ =P(Q), soQ ={ ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }.The start state ofMis thenE({1}) ={1,2}. The set of accept states ofMisF ={ {2},{1,2},{2,3},{1,2,3} }.We define the transitions in the DFAMas in the following diagram:3{1,2}{2,3} {1,2,3}ababa, bbaNote that we left out some of the states ( ,{1}) inP(Q)from our diagram of theDFAM since they are not accessible from the start state{1,2}.

4 Also, we had to addan arc from state to itself labelled with a, b so that this state has an arc leaving itcorresponding to each symbol in the alphabet , which is a requirement for any algorithm given in the notes and textbook will always correctly construct anequivalent DFA from a given NFA, but we don t always have to go through all thesteps of the algorithm to obtain an equivalent DFA. For example, on this problem, webegin by figuring out what states the NFA can be in without reading any symbols. Inthis case, this isE({1}) ={1,2}since1is the starting state of the NFA, and theNFA can jump from1to2without reading any symbols by taking the , we first create a DFA state corresponding to the set{1,2}:{1,2}The state{1,2}is the start state of the DFA since this is where the NFA can bewithout reading any symbols.

5 The state{1,2}is also an accepting state for the DFAsince it contains2, which is accepting for the for DFA state{1,2}, determine where the NFA can go on anafrom each NFAstate within this DFA state, and where the NFA can go on abfrom each NFA statewithin this DFA state. On ana, the NFA can go from state1to state3; also, theNFA can go from state2to1, and then it also can go further from1to2on the .So from NFA states1and2on ana, the NFA can end up in states1,2, and3, sodraw a transition in the DFA from state{1,2}to a new state{1,2,3}, which is anaccepting state since it contains2 F:4{1,2}{1,2,3}aSimilarly, to determine where the DFA moves onbfrom DFA state{1,2}, determineall the possibilities of where the NFA can go from NFA states1and2onb.

6 Fromstate1, the NFA can t go anywhere on ab; also, the NFA can t go anywhere fromstate2onb. Thus, the NFA can t go anywhere from states2and3on ab, so we addab-edge in the DFA from state{1,2}to a new DFA state , which is not acceptingsince it contains no accept states of the NFA:{1,2} {1,2,3}abNow every time we add a new DFA state, we have to determine all the possibilities ofwhere the NFA can go on anafrom each NFA state within that DFA state, and wherethe NFA can go on abfrom each NFA state within that DFA state. For DFA state{1,2,3}, we next determine where the NFA can go on anafrom each of the NFAstates1,2and3. From NFA state1, the NFA on anacan go to NFA state3; fromNFA state2, the NFA on anacan go to NFA state1, and then it can also furtherjump to2on ; from NFA state3, the NFA on anacan go to NFA state2.

7 Thus, ifthe NFA is in states1,2and3, it can go on anato states1,2and3, so we add tothe DFA ana-edge from{1,2,3}to{1,2,3}.{1,2} {1,2,3}abaNow we determine where theb-edge from DFA state{1,2,3}goes to. To do this,we examine what happens to the NFA from states1,2and3on ab. If the NFA isin state1, then there is nowhere to go on ab; if the NFA is in state2, then there isnowhere to go on ab; if the NFA is in state3, then the NFA can go , if the NFA is in states1,2and3, the NFA onbcan end in , in the DFA, draw an edge from state{1,2,3}to a new state{2,3}, which isaccepting since it contains2 F:5{1,2}{2,3} {1,2,3}abbaNow do the same for DFA states{2,3}and . If any new DFA states arise, then weneed to determine theaandbtransitions out of those states as well.

8 We stop onceevery DFA state has ana-transition and ab-transition out of it. Accepting statesin the DFA are any DFA states that contain at least one accepting NFA state. Weeventually end up with the DFA below as before:{1,2}{2,3} {1,2,3}ababa, bbaFor the DFA state , there are no versions of the NFA currently active, , all threads have crashed, so the NFA cannot proceed and the input string willnot be , according to the definition of a DFA, each state must have edges leaving itcorresponding to each symbol in the alphabet . Thus, we add a loop from the DFAstate back to itself labeled with , which in our case isa, Give regular expressions that generate each of the following languages.

9 In all cases,the alphabet is ={a, b}.6(a) The language{w | |w|is odd}.Answer:(a b)((a b)(a b)) (b) The language{w |whas an odd number ofa s}.Answer:b a(ab a b) (c) The language{w|wcontains at least twoa s, or exactly twob s}.Answer:b ab a(a b) a ba ba (d) The language{w |wends in a double letter}. (A string contains adoubleletterif it containsaaorbbas a substring.)Answer:(a b) (aa bb)(e) The language{w |wdoes not end in a double letter}.Answer: a b (a b) (ab ba)(f) The language{w |wcontains exactly one double letter}. For example,baabahas exactly one double letter, butbaaabahas two double :( b)(ab) aa(ba) ( b) ( a)(ba) bb(ab) ( a)5. Suppose we define a restricted version of the Java programminglanguage in whichvariable names must satisfy all of the following conditions: A variable name can only use Roman letters ( ,a,b.)

10 ,z,A,B, .. ,Z) orArabic numerals ( ,0,1,2, .. ,9); , underscore and dollar sign are notallowed. A variable name must start with a Roman letter:a,b, .. ,z,A,B, .. ,Z The length of a variable name must be no greater than 8. A variable name cannot be a keyword ( , if). The set of keywords the set of all valid variable names in our restricted version of Java.(a) LetL0be the set of strings satisfying the first 3 conditions above; , we do notrequire the last condition. Give a regular expression :To simplify the regular expression, we define 1={a,b, .. ,z,A,B, .. ,Z} 2={0,1,2, .. ,9}.Then a regular expression forL0is 1( 1 2 ) ( 1 2 ) 7 that by including the in each of the last parts, we can generate stringsthat have length strictly less than (b) Prove thatLhas a regular expression, whereLis the set of strings satisfying allfour :We proved in Homework 1, problem 4(b), thatLis finite.