Теория и 2 задачи

Теоретический вопрос.
Лексический блок. Конечные распознающие автоматы. Определение. Три примера: 1) проверка на четность строки из {0,1}; 2) поиск парного символа; 3) проверка на использование парного символа. Процессор, редукция
Постройте конечный автомат, реализующий лексический блок, распознающий текст, составлен-ный из 45 слов: один, два, три, ... , девять, десять, одиннадцать, ... девятнадцать, двадцать, тридцать, ... , девяносто, сто, двести, триста, ... , девятьсот, тысяча, тысячи, тысяч, миллион, миллиона, мил-лионов, миллиард, миллиарда, миллиардов. Слова разделяются одним или несколькими пробелами. На выходе лексического блока каждое слово заменяется символом с ASCII кодом, равным c + N, где c = 96, а N – номер слова в списке (пробелы выбрасываются). Автомат должен быть реализован при помощи динамического списка
В задачах 22 реализовать интерпретатор, используя атрибутную грамматику
22. В условиях задачи 1 к операндам добавить переменную x. (Тем самым реализуются рациональные функции.)