1. Using the algorithm discussed in class, show the transition diagram for a pushdown automation to recognize the language generated by these grammar rules. Specify rest of PDA fully.

S -> bA

S -> bB

A -> aA

A -> e

B -> bB

B -> e

b) Describe in english the language generated by the above grammer

2. Show how a PDA Transition like q-> (a,b->xyz) r would be implemented if only one symbol can be pushed at a time.

3. Give the state diagram of a standard Turing Maching to decide strings over {a,b}* that contain the substring bba. Show all states on the state diagram and define the rest of the TM fully.

b) What must be included in a configuration of TM