• Ch. 8 discusses adding "output" to a FA to create a FA transducer
• we can do the same thing with PDA’s
• creating a pushdown (or PDA) transducer

• a PRINT box
• which can follow any READ or POP
• and will print whatever was read or popped

Infix notation:

• conventional notation
• uses "order of operations" rules for evaluation
• for 2 + 3*5 , "*" must be done first
• rules are called operator precedence or operator hierarchy or operator priority rules
• parentheses are used to override precedences: (2 + 3)*5

• operands in same order, but no parentheses
• operators "follow" operands: 1 + 3 Þ 1 3 +
• 2 + 3*5 = 2 3 5 * +
• (2 + 3)*5 = 2 3 + 5 *

1. Operators cannot be printed until after the operands are seen: e.g. a + b Þ ab+ . So we will save operators when we read them, and print them later. We will save them on the stack
2. Think about a + b * c * d + e + f .

The red * would have been saved on the top of the stack until after the c is read. It can be printed at that point, regardless of what operator comes before or after, because * has higher precedence that +.  We would end up printing the subexpression bc* (which is correct).
3. Think about:   a + b * c * d + e + f .

The red + would have been saved on the top of the stack until after the b is read. It cannot be printed at that point, because * has higher precedence than +. We will have to:
• push the * on top of the +
• print the + when another + (or the end of the string) is seen

Here is a PDA that implements the above idea for

• three operands: a, b, c
• two operators: +, *

Let’s follow the workings of this machine for some sample input (the stack is shown after reading an operator; the top of the stack is to the right):
 

input		a	+	b	*	c	D
stack	D		+		+*		D
print		a		b		c	*+

a+b*c Þ abc*+
 

input		a	*	b	+	c	D
stack	D		*		+		D
print		a		b	*	c	+

a*b+c Þ ab*c+
 

input		a	+	b	*	c	*	d	+	e	D
stack	D		+		+*		+*		+		D
print		a		b		c	*	d	*+	e	+

a+b*c*d+e Þ abc*d*+e+

Here is the scheme:

• read a left paren Þ push it onto the stack
• read a right paren Þ proceed as we would have for end of string. Pop the left paren at the top of the stack (reject if none there)