Формальные языки


Первичные понятия


Определение. Конечное множество символов, неделимых в данном рассмотрении, называется словарем

или алфавитом, а символы, входящие в множество, - буквами алфавита.

    Например, алфавит 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*.

 

Определение.  Формальной порождающей грамматикой




- Начало -  - Назад -  - Вперед -