[PDF] Homework 5 Solutions

View - Download Homework 5 Solutions

Previous PDF

Next PDF

CS 341: Foundations of Computer Science II

Prof. Marvin Nakayama

Homework 5 Solutions

1. Give context-free grammars that generate the following languages.

(a){w? {0,1}?|wcontains at least three1s} Answer:G= (V,Σ,R,S)with set of variablesV={S,X}, whereSis the start variable; set of terminalsΣ ={0,1}; and rules

S→X1X1X1X

X→0X|1X|ε

(b){w? {0,1}?|w=wRand|w|is even} Answer:G= (V,Σ,R,S)with set of variablesV={S}, whereSis the start variable; set of terminalsΣ ={0,1}; and rules

S→0S0|1S1|ε

(c){w? {0,1}?|the length ofwis odd and the middle symbol is0} Answer:G= (V,Σ,R,S)with set of variablesV={S}, whereSis the start variable; set of terminalsΣ ={0,1}; and rules

S→0S0|0S1|1S0|1S1|0

(d){aibjck|i,j,k≥0, andi=jori=k} Answer:G= (V,Σ,R,S)with set of variablesV={S,W,X,Y,Z}, where Sis the start variable; set of terminalsΣ ={a,b,c}; and rules

S→XY|W

X→aXb|ε

Y→cY|ε

W→aWc|Z

Z→bZ|ε

1 (e){aibjck|i,j,k≥0andi+j=k} Answer:G= (V,Σ,R,S)with set of variablesV={S,X}, whereSis the start variable; set of terminalsΣ ={a,b,c}; and rules

S→aSc|X

X→bXc|ε

(f){aibjck|i,j,k≥0andi+k=j} Answer:LetL={aibjck|i,j,k≥0andi+k=j}be the language given in the problem, and define other languages L

1={aibi|i≥0},

L

2={bkck|k≥0}.

Note thatL=L1◦L2because concatenating any stringaibi?L1with any stringbkck?L2results in a stringaibibkck=aibi+kck?L. Thus, ifL1has a CFGG1= (V1,Σ,R1,S1), andL2has a CFGG2= (V2,Σ,R2,S2), we can construct a CFG forL=L1◦L2by using the approach in problem 3b, as suggested in the hint. Specifically, •L1has a CFGG1= (V1,Σ,R1,S1), withV1={S1},Σ ={a,b,c},S1 as the starting variable, and rulesS1→aS1b|εinR1; •L2has a CFGG2= (V2,Σ,R2,S2), withV2={S2},Σ ={a,b,c},S2 as the starting variable, and rulesS2→bS2c|εinR2. Even thoughΣ ={a,b,c}for both CFGsG1andG2, CFGG1never generates a string withc, and CFGG2never generates a string witha. Then from problem

3b, a CFGG3= (V3,Σ,R3,S3)forLhasV3=V1?V2?{S3}={S1,S2,S3}

withS3the starting variable,Σ ={a,b,c}, and rules S

3→S1S2

S

1→aS1b|ε

S

2→bS2c|ε

(g)∅Answer:G= (V,Σ,R,S)with set of variablesV={S}, whereSis the start variable; set of terminalsΣ ={0,1}; and rules

S→S

Note that if we start a derivation, it never finishes, i.e.,S?S?S? ···, so no string is ever produced. Thus,L(G) =∅. (h) The languageAof strings of properly balanced left and right brackets: every left bracket can be paired with a unique subsequent right bracket, andevery right 2 bracket can be paired with a unique preceding left bracket. Moreover, the string between any such pair has the same property. For example,[][[[][]][]]?A. Answer:G= (V,Σ,R,S)with set of variablesV={S}, whereSis the start variable; set of terminalsΣ ={[,]}; and rules

S→ε|SS|[S]

2. LetT={0,1,(,),?,?,∅, e}. We may think ofTas the set of symbols used by

regular expressions over the alphabet{0,1}; the only difference is that we useefor symbolε, to avoid potential confusion in what follows. (a) Your task is to design a CFGGwith set of terminalsTthat generates exactly the regular expressions with alphabet{0,1}. Answer:G= (V,Σ,R,S)with set of variablesV={S}, whereSis the start variable; set of terminalsΣ =T; and rules

S→S?S|SS|S?|(S)|0|1| ∅ |e

(b) Using your CFGG, give a derivation and the corresponding parse tree for the string(0?(10)?1)?.

Answer:A derivation for(0?(10)?1)?is

S?S??(S)??(S?S)??(0?S)??(0?SS)??(0?S?S)?

?(0?(S)?S)??(0?(SS)?S)??(0?(1S)?S)? ?(0?(10)?S)??(0?(10)?1)? and the corresponding parse tree is 3 S S (S) S?S 0S S S?1 (S) S S 1 0

3. (a) Suppose that languageA1has a context-free grammarG1= (V1,Σ,R1,S1),

and languageA2has a context-free grammarG2= (V2,Σ,R2,S2), where, for i= 1,2,Viis the set of variables,Riis the set of rules, andSiis the start variable for CFGGi. The CFGs have the same set of terminalsΣ. Assume thatV1∩V2= ∅. Define another CFGG3= (V3,Σ,R3,S3)withV3=V1?V2?{S3}, where S

3??V1?V2, andR3=R1?R2? {S3→S1, S3→S2}. Argue thatG3

generates the languageA1?A2. Thus, conclude that the class of context-free languages is closed under union. Answer:LetA3=A1?A2, and we need to show thatL(G3) =A3. To do this, we need to prove thatL(G3)?A3andA3?L(G3). To show that L(G3)?A3, first consider any stringw?L(G3). Sincew?L(G3), we have thatS3??w. Since the only rules inR3withS3on the left side are S

3→S1|S2, we must have thatS3?S1??worS3?S2??w. Suppose

first thatS3?S1??w. SinceS1?V1and we assumed thatV1∩V2=∅, the derivationS1??wmust only use variables inV1and rules inR1, which implies thatw?A1. Similarly, ifS3?S2??w, then we must have thatw?A2.

Thus,w?A3=A1?A2, soL(G3)?A3.

To show thatA3?L(G3), first suppose thatw?A3. This impliesw?A1or w?A2. Ifw?A1, thenS1??w. But thenS3?S1??w, sow?L(G3). 4 Similarly, ifw?A2, thenS2??w. But thenS3?S2??w, sow?L(G3). Thus,A3?L(G3), and since we previously showed thatL(G3)?A3, it follows thatL(G3) =A3; i.e., the CFGG3generates the languageA1?A2. (b) Prove that the class of context-free languages is closed under concatenation. Answer:Suppose that languageA1has a context-free grammarG1= (V1,Σ,R1,S1), and languageA2has a context-free grammarG2= (V2,Σ,R2,S2), where, for i= 1,2,Viis the set of variables,Riis the set of rules, andSiis the start variable for CFGGi. The CFGs have the same set of terminalsΣ. Assume thatV1∩V2=∅. Then a CFG forA1◦A2isG3= (V3,Σ,R3,S3)with V

3=V1?V2?{S3}, whereS3??V1?V2, andR3=R1?R2?{S3→S1S2}.

To understand whyL(G3) =A1◦A2, note that any stringw?A1◦A2can be written asw=uv, whereu?A1andv?A2. It follows thatS1??uand S

2??v, soS3?S1S2??uS2??uv, sow=uv?L(G3). This proves that

A

1◦A2?L(G3).

To prove thatL(G3)?A1◦A2, consider any stringw?L(G3). Sincew? L(G3), it follows thatS3??w. The only rule inR3withS3on the left side is S

3→S1S2, soS3?S1S2??w. SinceV1∩V2=∅, any derivation starting

fromS1can only generate a string inA1, and any derivation starting fromS2 can only generate a string inA2. Thus, sinceS3?S1S2??w, it must be that wis the concatenation of a string fromA1with a string fromA2. Therefore, w?A1◦A2, which establishes thatL(G3)?A1◦A2. (c) Prove that the class of context-free languages is closed under Kleene-star. Answer:Suppose that languageAhas a context-free grammarG1= (V1,Σ,R1,S1). Then a CFG forA?isG2= (V2,Σ,R2,S2)withV2=V1? {S2}, where S

2??V1, andR2=R1? {S2→S1S2, S2→ε}.

To show thatL(G2) =A?, we first prove thatA??L(G2). Consider any stringw?A?. We can writew=w1w2···wnfor somen≥0, where each w i?A. (Here, we interpretw=w1w2···wnforn= 0to bew=ε.) Since eachwi?A, we have thatS1??wi. To derive the stringwusing CFGG2, we first apply the ruleS2→S1S2a total ofntimes, followed by one application of the ruleS2→ε. Then for theithS1, we useS1??wi. Thus, we get S

2??S1S1···S1?

ntimesS

2?S1S1···S1????

ntimes? ?w1w2···wn=w

Therefore,w?L(G2), soA??L(G2).

To show thatL(G2)?A?, suppose we apply the ruleS→S1S2a total of n≥0times, followed by an application of the ruleS2→ε. This gives S

2??S1S1···S1?

ntimesS

2?S1S1···S1????

ntimes. 5 Now each of the variablesS1can be used to derive a stringwi?A, i.e., from the ithS1, we getS1??wi. Thus, S

2??S1S1···S1?

ntimes? ?w1w2···wn?A? since eachwi?A. Therefore, we end up with a string inA?. To convince ourselves that the productions applied to the various separateS1terms do not interfere in undesired ways, we need only think of the parse tree. EachS1is the root of a distinct branch, and the rules along one branch do not affect those on another. Here, we assumed that we first applied the ruleS2→S1S2a total of ntimes, then applied the ruleS2→ε, and then applied rules to change each S

1into strings. However, we could have applied the rules in a different order, as

long as the ruleS2→εis applied only after thenapplications ofS2→S1S2. By examining the parse tree, we can argue as before that the order in which we applied the rules doesn"t matter.

4. Convert the following CFG into an equivalent CFG in Chomsky normalform, using

the procedure given in Theorem 2.9.

S→BSB|B|ε

B→00|ε

Answer:First introduce new start variableS0and the new ruleS0→S, which gives S

0→S

S→BSB|B|ε

B→00|ε

Then we removeεrules:

•RemovingB→εyields S

0→S

S→BSB|BS|SB|S|B|ε

B→00

•RemovingS→εyields S

0→S|ε

S→BSB|BS|SB|S|B|BB

B→00

•We don"t need to remove theε-ruleS0→εsinceS0is the start variable and that is allowed in Chomsky normal form. 6

Then we remove unit rules:

•RemovingS→Syields S

0→S|ε

S→BSB|BS|SB|B|BB

B→00

•RemovingS→Byields S

0→S|ε

S→BSB|BS|SB|00|BB

B→00

•RemovingS0→Sgives S

0→BSB|BS|SB|00|BB|ε

S→BSB|BS|SB|00|BB

B→00

Then we replaced ill-placed terminals0by variableUwith new ruleU→0, which gives S

0→BSB|BS|SB|UU|BB|ε

S→BSB|BS|SB|UU|BB

B→UU

U→0

Then we shorten rules with a long RHS to a sequence of RHS"s with only 2variables each. So the ruleS0→BSBis replaced by the 2 rulesS0→BA1andA1→SB. Also the ruleS→BSBis replaced by the 2 rulesS→BA2andA2→SB. Thus, our final CFG in Chomsky normal form is S

0→BA1|BS|SB|UU|BB|ε

S→BA2|BS|SB|UU|BB

B→UU

U→0

A

1→SB

A

2→SB

To be precise, the CFG in Chomsky normal form isG= (V,Σ,R,S0), where the set of variables isV={S0,S,B,U,A1,A2}, the start variable isS0, the set of terminals isΣ ={0}, and the rulesRare given above. 7

5. (a) The CFGGderives the string- - -5as

S? -S? - -S? - - -S? - - -5

so- - -5?L(G). The CFGGderives the string2 +- -4as

S?S+S?S+-S?S+- -S?2 +- -S?2 +- -4

so2 +- -4?L(G). (b) To prevent generating strings such as in part (a), we can use the CFGG?= (V?,Σ,R?,S), whereV?={S,N}is the set of variables withSas the starting variable, alphabetΣ ={+,-,×,/,(,),0,1,2,...,9}, and rulesR?as

S→S+S|S-S|S×S|S/S|(S)|N| -N

N→0|1| ··· |9

8quotesdbs_dbs14.pdfusesText_20

[PDF] find a regular expression for the set a^nb^m (n+m) is odd

[PDF] find a regular expression for the set {anbm:( n + m) is even}.

[PDF] find a regular grammar that generates the language l (aa* (ab+ a)*).

[PDF] find all complex solutions calculator

[PDF] find an inmate

[PDF] find coinbase account number

[PDF] find connected components in directed graph

[PDF] find death notices

[PDF] find degree of vertex in graph

[PDF] find my 1099 misc online

[PDF] find my twitter account

[PDF] find object type javascript

[PDF] find octagonal prism volume

[PDF] find perfect square trinomial calculator

[PDF] find the basic feasible solution