This chapter presents the following content: Example of ambiguous grammar, example of unambiguous grammer (Palindrome), total language tree with examples (Finite and infinite trees), regular grammar, FA to CFG, semi word and word, theorem, defining regular grammar, method to build TG for regular grammar. | Recap lecture 33 Example of trees, Polish Notation, examples, Ambiguous CFG, example, Solution of the Task Convert the following infix expressions into the corresponding prefix expressions. Calculate the values of the expressions as well 2*(3+4)*5 Solution: 2*+3 4 *5 which can be calculated as *2+3 4 *5 = * *2+3 4 5= **2 7 5 = *14 5 = 70 ((4+5)*6)+4 Solution: (+4 5 * 6)+4= (*+4 5 6) + 4 which can be calculated as +*+4 5 6 4 = +* 9 6 4 = +54 4 = 58 Example Consider the following CFG S aS | bS | aaS | It can be observed that the word aaa can be derived from more than one production trees. Thus, the above CFG is ambiguous. This ambiguity can be removed by removing the production S aaS Following is another example Example Consider the CFG of the language PALINDROME S aSa|bSb|a|b| It may be noted that this CFG is unambiguous as all the words of the language PALINDROME can only be generated by a unique production tree. It may be noted that if the production S aaSaa is added to the | Recap lecture 33 Example of trees, Polish Notation, examples, Ambiguous CFG, example, Solution of the Task Convert the following infix expressions into the corresponding prefix expressions. Calculate the values of the expressions as well 2*(3+4)*5 Solution: 2*+3 4 *5 which can be calculated as *2+3 4 *5 = * *2+3 4 5= **2 7 5 = *14 5 = 70 ((4+5)*6)+4 Solution: (+4 5 * 6)+4= (*+4 5 6) + 4 which can be calculated as +*+4 5 6 4 = +* 9 6 4 = +54 4 = 58 Example Consider the following CFG S aS | bS | aaS | It can be observed that the word aaa can be derived from more than one production trees. Thus, the above CFG is ambiguous. This ambiguity can be removed by removing the production S aaS Following is another example Example Consider the CFG of the language PALINDROME S aSa|bSb|a|b| It may be noted that this CFG is unambiguous as all the words of the language PALINDROME can only be generated by a unique production tree. It may be noted that if the production S aaSaa is added to the given CFG, the CFG thus obtained will be no more unambiguous. Total language tree For a given CFG, a tree with the start symbol S as its root and whose nodes are working strings of terminals and non-terminals. The descendants of each node are all possible results of applying every production to the working string. This tree is called total language tree. Following is an example of total language tree Example Consider the following CFG S aa|bX|aXX X ab|b, then the total language tree for the given CFG may be S aa bX aXX bab bb aabX abX aXab aXb aabab aabb aabab abab aabb abb abab abb Example continued It may be observed from the previous total language tree that dropping the repeated words, the language generated by the given CFG is {aa, bab, bb, aabab, aabb, abab, abb} Example Consider the following CFG S X|b, X aX then following will be the total language tree of the above CFG Note: It is to be noted that the only word in this language is b. S X b aX aaX aaa aX Regular .
