1. Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to context-free grammar. Show, step by step, how the word a01 will be accepted by this automaton. In this grammar, N stands for names, L for letters, and D for digits. The rules are: N L, N NL, N ND, L a, D 0, and D 1.

2. Transform the grammar into Chomsky normal form. Grammar: N L, N NL, N ND, L a, D 0, and D 1.

3. Use the general algorithm to transform the pushdown automaton into a context-free grammar. Show, step-by-step, how the resulting grammar will generate the word IDII.

Pushdown Automaton This pushdown automaton has three states:

the starting state s,

the working state w, and

the final state f.

In the stack, in addition to the bottom symbol $, we have:

either one or several I's -- indicating by how much the price of the stock increased so far,

or one or several D's -- indicating by how much the price of the stock decreased so far.

The transitions are as follows:

From s to w, the transition is , $.

From w to f, the transition is: , I .

From f to f, we have two transitions: , I and , $ .

From w to w, we have the following transitions:

If we see the symbol I and $ is on top of the stack, we keep the dollar sign and add I to the stack, i.e., we have transition I, $ $ that brings us to an intermediate state a₁, and then the transition , I that brings us back to the working state.

If we see the symbol I and I is on top of the stack, we keep the top I and add another I to the stack, i.e., we have transition I, I I that brings us to an intermediate state a₂, and then the transition , I that brings us back to the working state.

If we see the symbol I and D is on top of the stack, we delete the top D, i.e., we have transition I, D .

If we see the symbol D and $ is on top of the stack, we keep the dollar sign and add D to the stack, i.e., we have transition D, $ $ that brings us to an intermediate state a₃, and then the transition , D that brings us back to the working state.

If we see the symbol D and D is on top of the stack, we keep the top D and add another D to the stack, i.e., we have transition D, D Dthat brings us to an intermediate state a₄, and then the transition , D that brings us back to the working state.

If we see the symbol D and I is on top of the stack, we delete the top I, i.e., we have transition D, I .