In this chapter, the following content will be discussed: Task, solution of the task, example, polish notation, Ambiguous CFG, example, deciding whether an FA accept any string or not, method 3, examples, finiteness of a language, CFG, context Free language, examples. | Task Construct CFG that generates the language L = {w {a,b}*: length(w) 2 and second letter of w from right is a} Solution of the task Construct CFG that generates the language L = {w {a,b}*: length(w) 2 and second letter of w from right is a} It can be observed that the language L can be expressed by (a+b)*(aa+ab). Here the nonterminal S should be replaced the nonterminals X or Y where X should generate the strings corresponding to (a+b)* and Y should generate the strings corresponding to (aa+ab). Thus the required CFG may be (1) S XY (2) X aX|bX| (3) Y aa|ab Task Construct the CFG for the language of strings, defined over ={a,b}, beginning and ending in same letters. Solution: It may be noted that the above language contains the strings a and b as well. So while constructing the required CFG the strings a and b must be generated. Thus the required CFG may be S aXa|bXb|a|b X aX|bX| Example Consider the following CFG S S+S|S*S|number where S and number are . | Task Construct CFG that generates the language L = {w {a,b}*: length(w) 2 and second letter of w from right is a} Solution of the task Construct CFG that generates the language L = {w {a,b}*: length(w) 2 and second letter of w from right is a} It can be observed that the language L can be expressed by (a+b)*(aa+ab). Here the nonterminal S should be replaced the nonterminals X or Y where X should generate the strings corresponding to (a+b)* and Y should generate the strings corresponding to (aa+ab). Thus the required CFG may be (1) S XY (2) X aX|bX| (3) Y aa|ab Task Construct the CFG for the language of strings, defined over ={a,b}, beginning and ending in same letters. Solution: It may be noted that the above language contains the strings a and b as well. So while constructing the required CFG the strings a and b must be generated. Thus the required CFG may be S aXa|bXb|a|b X aX|bX| Example Consider the following CFG S S+S|S*S|number where S and number are non-terminals and the operators behave like terminals. The above CFG creates ambiguity as the expression 3+4*5 has two possibilities (3+4)*5=35 and 3+(4*5)=23 which can be expressed by the following production trees Example continued S S S S S 3 4 + * 5 (i) S S 5 * (ii) S S S 3 + 4 Example continued The expressions can be calculated starting from bottom to the top, replacing each nonterminal by the result of calculation . S 3 S 4 5 + * (i) S 3 20 + 23 Example continued Similarly The ambiguity that has been observed in this example can be removed with a change in the CFG as discussed in the following example S 5 * (ii) S 7 5 * 35 S 3 4 + Example S (S+S)|(S*S)|number where S and number are nonterminals, while (, *, +, ) and the numbers are terminals. Here it can be observed that S (S+S) (S+(S*S)) (3+(4*5)) = 23 S (S*S) ((S+S)*S) ((3+4)*5) = 35 Polish Notation (o-o-o) There is another notation for arithmetic expressions for the CFG S S+S|S*S|number. Consider the
