На этом шаге мы перечислим эти операции.

Вспомним следующие обозначения:

(1) A - алфавит, A⁺ - множество всех непустых слов в алфавите A, A^* - множество всех слов в алфавите A, включая ε (пустое слово);

(2) a ∈ A, α ∈ A^*;

(3) +: A × A^*→ A^* - операция левого присоединения буквы из A к слову в A.

Определение.: (1) Головой слова из A⁺ назовём отображение Head: A⁺→ A, если Head (a + α) ⇔ a.
(2) Хвостом слова из A⁺ назовём отображение Tail: A⁺→ A^*, если Tail (a + α) ⇔ α.

На следующем шаге мы приведем примеры некоторых типов упражнений.