Question

Suppose an elevator is controlled by two commands: ↑ to move the elevator up one floor and ↓ to move the elevator down one floor. Assume that the building is arbitrarily tall and that the elevator starts at floor x.

A)Write an LL(1) grammar that generates arbitrary command sequences that (1) never cause the elevator to go below floor x and (2) always return the elevator to floor x at the end of the sequence. For example, ↑↑↓↓ and ↑↓↑↓ are valid command sequences, but ↑↓↓↑ and ↑↓↓ are not. For convenience, you may consider a null sequence as valid.

B)Prove that your grammar is LL(1) (you need to provide the first, follow, and predict sets, as well as the complete parse table).

Answer 1

he question is quite interesting, we will use reduction method to solve the problem:-

Generally when we come across problems like these we have to reduce the problem accoring to logic, like, from this question, we can understand the hidden logics, which will make the question more easy:-

1) We observer that the machine should start and end at a fixed state.

2) If we assume that ↑ = a & ↓ = b , then we can reduce this problem by saying, that this problem talks about a language wich has equal number of a's and b's.

Now lets solve for it:-

Here, we need not to maintain any order of a’s and b’s. Thus our state diagram will contain only an initial state and a final state. The count of a’s and b’s is maintained by stack. We will take 3 stack alphabets:

  = {a, b, z}

1. If ‘a’ comes first then push it in stack
2. if again ‘a’ comes then also push it
3. Similarly, if ‘b’ comes first (‘a’ did not comes yet) then push it into the stack
4. if again ‘b’ comes then also push it.
5. if ‘a’ is present in the top of the stack and ‘b’ comes then pop the ‘a’ from the stack.
6. if ‘b’ present in the top of the stack and ‘a’ comes then pop the ‘b’ from the stack.
7. And at the end if the stack becomes empty then we can say that the string is accepted.

where a = ↑ & b =  ↓ and x = Initial state , xf = Final state and similarly = indicates pop operation