a. (10 points) Suppose that the input string is the car arrived. At the point when the word the first enters the input window, what are the contents of the stack?

b. (10 points) Suppose that the NPDA accepts an input string if (and only if) it reaches the end of the input and, at that point, is in the STOP state. Does the NPDA accept the string the boy left the car? Explain how you arrived at your answer.

7. Consider the following Non-deterministic Push-Down Automaton (NPDA) INPUT FSA The box at the left is an "input" window. The FSA controlling the device can perform four distinct actions . When the FSA performs the "Read" action, it causes the next word (if any) of the input to be moved into the 'input' window; . The action "Delete" erases the current contents of the input window; . An action like "Push S" causes the symbol "S" to become the topmost element in the stack; and . The action "Pop" causes whatever is currently at the top of the stack to be removed and deleted The FSA begins operation in the START state, with nothing in the stack and nothing in the input window. If the FSA enters the STOP state, all its operations cease. The following is the FSA's State Transition Table (Rule) Current state Top of stackInputActions ext state START Push S Pop; Push VP; Push NP Pop; Push N; Push D; ReadNPs NPs NPs NPs NPs the Pop; Delete; Read boy Pop; Delete car Pop; Delete VP Pop; Push V; Read VPs VPs arrived Pop; Delete VPs left Pop; Delete (10) STOP