Describe the language generated by the grammarG S where10p

. Describe the language generated by the grammarG = {,,S,}, where10pts = {0,1}, = {S,X,Y,Z} and = {S 0X|1Y,X 1Y|1Z,Y 0X|0Z,Z 0|}. Hint:Make a diagram of the productions.

Solution

Ans-

E T | E + T (1) E\' E + T (2) T id | T\' * F (3) T\' F | T\' * F (4) F id | (E\') (5) Explanation: Parentheses can be redundant for three reasons: (i) they embrace a product or an atomic id, or (ii) they embrace the entire expression, or (iii) they embrace a sum that is not preceded or followed by a *. Our grammar precludes all three possibilities: (i) parentheses can only be introduced with rule (5), which leads to rule (2), which enforces a + inside parentheses. (ii): Parentheses can only be introduced by rule (5), which needs a prior derivation of F, which can only be introduced together with a * by (3) or via T\', which itself comes with a * in (3). (iii): same argument as for (ii); ensures that a * must come before or after parentheses. Derivation of (id + id) * id: E T T\' * F F * F * (E\') * id * (id + id) * id Derivation of id * (id + id): E T T\' * F F * F * id * (E\') * id * (id + id) Exercise 5. (15 points) Design a PDA for the language L of words over the terminal alphabet T = {(,)} that belong to the language of the grammar S S S | (S) | . (This is the language of all \"balanced parenthesis\" words). The PDA should accept by going into an accepting state. Specify your PDA by its transition function, and describe the principles behind your design in intuitive terms. Solution. Intuitive description: the PDA may, at any time and regardless of top stack symbol, read in an opening \"(\" and memorizes the opening by pushing one \")\" on the stack. It may read in a \")\" only if an \")\" is the top stack symbol, which is then deleted. When the bottom stack symbol Z0 is seen, the PDA may enter an accepting state with input.