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:

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.