1. Suppose that someone marks every time the price of a share increases (I) by $1 and decreases (D) by $1. As a result, you get a sequence like IDII. Based on the sequence, we want to detect whether eventually, the price increased, i.e., whether the sequence contained more increases than decreases. Prove that the language of all the sequences corresponding to eventual increase is not regular.

2. Show, step by step, how the following pushdown automaton -- that checks whether a word consisting of letters I and D describes a share whose price increases -- will accept the word IDII. 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 .

3. Show, step by step, how the following grammar describing valid names for variables in an alphabet consisting of 0, 1, and a will generate the word a01. 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.