# Question PART 2 [DESIGN PUSH DOWN AUTOMATA] Whenever your smartphone calculator calculates an arithmetic expression, it uses an implementation of the push down automata to evaluate it: It verifies that the parentheses are balanced. If you are not using parenthesis, it makes sure that the multiplication operator has more precedence than the addition or subtraction operator. All this can be summarized in three lines of grammar: • E-E+TIE-TIT • T-TFIT/EF F-XIy (E)-F The first rule is the starting point of any evaluation. Observe that the multiplication and division operations cannot be evaluated unless the PDA implementation sees Tor F. This ensures the precedence of multiplication division over addition/subtraction. Also observe that F produces another E (expression) only if it is wrapped in parentheses. This allows us to override the precedence of multiplication and division operations using parentheses. You need to design a PDA modeling the behavior of this system. Your PDA will be a single state PDA aceepting on empty stack. The alphabet is 8:{+;--(),0,1,2,3,4,5,6,7,8,9} You do not need to submit your design but, on APRIL 1", 2021, you will take a 15-minutes demo on blackboard with 5 MCQs about your design. If your design is correct, you will be able to answer the questions correctly.

TMAZ4Z The Asker · Computer Science

Transcribed Image Text: PART 2 [DESIGN PUSH DOWN AUTOMATA] Whenever your smartphone calculator calculates an arithmetic expression, it uses an implementation of the push down automata to evaluate it: It verifies that the parentheses are balanced. If you are not using parenthesis, it makes sure that the multiplication operator has more precedence than the addition or subtraction operator. All this can be summarized in three lines of grammar: • E-E+TIE-TIT • T-TFIT/EF F-XIy (E)-F The first rule is the starting point of any evaluation. Observe that the multiplication and division operations cannot be evaluated unless the PDA implementation sees Tor F. This ensures the precedence of multiplication division over addition/subtraction. Also observe that F produces another E (expression) only if it is wrapped in parentheses. This allows us to override the precedence of multiplication and division operations using parentheses. You need to design a PDA modeling the behavior of this system. Your PDA will be a single state PDA aceepting on empty stack. The alphabet is 8:{+;--(),0,1,2,3,4,5,6,7,8,9} You do not need to submit your design but, on APRIL 1", 2021, you will take a 15-minutes demo on blackboard with 5 MCQs about your design. If your design is correct, you will be able to answer the questions correctly.
More
Transcribed Image Text: PART 2 [DESIGN PUSH DOWN AUTOMATA] Whenever your smartphone calculator calculates an arithmetic expression, it uses an implementation of the push down automata to evaluate it: It verifies that the parentheses are balanced. If you are not using parenthesis, it makes sure that the multiplication operator has more precedence than the addition or subtraction operator. All this can be summarized in three lines of grammar: • E-E+TIE-TIT • T-TFIT/EF F-XIy (E)-F The first rule is the starting point of any evaluation. Observe that the multiplication and division operations cannot be evaluated unless the PDA implementation sees Tor F. This ensures the precedence of multiplication division over addition/subtraction. Also observe that F produces another E (expression) only if it is wrapped in parentheses. This allows us to override the precedence of multiplication and division operations using parentheses. You need to design a PDA modeling the behavior of this system. Your PDA will be a single state PDA aceepting on empty stack. The alphabet is 8:{+;--(),0,1,2,3,4,5,6,7,8,9} You do not need to submit your design but, on APRIL 1", 2021, you will take a 15-minutes demo on blackboard with 5 MCQs about your design. If your design is correct, you will be able to answer the questions correctly.