Первичные понятия
| Определение. Конечное множество символов, неделимых в данном рассмотрении, называется словарем
или алфавитом, а символы, входящие в множество, - буквами алфавита. |
- Например, алфавит A = {a, b, c, +, !}
содержит 5 букв, а алфавит B = {00, 01, 10, 11}
содержит 4 буквы, каждая из которых состоит из двух символов.
| Определение. Последовательность букв алфавита называется словом или цепочкой
в этом алфавите. Число букв, входящих в слово, называется его длиной. |
- Например, слово в алфавите A a=ab++c
имеет длину l(a) = 5, а слово в алфавите B b=00110010 имеет длину l (b) = 4.
Если задан алфавит A, то обозначим
A* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A*.
Определение. Формальной порождающей грамматикой
|