## CS 3350
Automata, Computability, and Formal Languages

Fall 2018, Quiz
10

Last 4 digits of your UTEP ID number:
____________________________
1. The following is a simple example of an LL(2) context-free
language, in which we need to move two steps ahead to determine
which rule to apply. In this example, we have the following rules:
(1) S → aaA, (2) S → abA, (3) A → c. When we are in
the state S and see only one letter of the word, we do not know
which of the first two rules to apply. However, if we see two next
letters, we know which rule to apply:

- if we are in the
state S and we see aa, we apply Rule 1;
- if we are in the
state S and we see ab, we apply Rule 2;
- if we are in the
state A, we apply Rule 3.

Use the general algorithm to
transform the above grammar into a push-down automaton. Then, use
the above rules to check that the word abc is accepted by this
grammar; show your checking process step by step.