Вывод цепочек

Цепочкой символов (строкой символов) называют произвольную упорядоченную конечную последовательность символов, записанных один за другим.

Цепочка символов является последовательностью, в которую могут входить любые допустимые символы. Поскольку цепочка символов является упорядоченной последовательностью, значит, определяющее значение имеют следующие факторы: состав входящих в цепочку символов, количество символов, составляющих цепочку и порядок символов в цепочке.

Над цепочками символов можно выполнять следующие операции:

Конкатенация(сложение, объединение) двух цепочек символов — это дописывание второй цепочки в конец первой. Конкатенация цепочек α и β обозначается αβ. Поскольку для цепочек важен порядок символов, следовательно αβ <> βα.

Обращение цепочки— запись цепочки символов в обратном порядке. Обращение цепочки α обозначается α^R. Т.е., если α= 0101, то α^R = 1010.

Итерация(повторение) цепочки n раз — конкатенация цепочки самой с собой n раз. Итерация цепочки α n раз обозначается как αⁿ.

Пустая цепочка символов — цепочка, не содержащая ни одного символа (обозначается символами e или ε).

Выводомназывается процесс порождения цепочек языка на основе правил, входящих в состав грамматики данного. Непосредственно выводимой цепочкой называется цепочка, которая получается из текущей, после применения только одного какого-то правила вывода. Последовательность непосредственно выводимых цепочек — цепочка вывода. Например, в школе, при решении задач по физике, алгебре или геометрии, часто просят решить задачу аналитически, т. е. на основе нескольких базовых отношений (формул) необходимо вывести с помощью законов алгебры конечное выражение, в котором бы использовались только известные исходные данные. В данном примере: законы алгебры являются правилами вывода, а сами формулы — цепочками символов какого то алфавита (условных обозначений принятых в той или иной предметной области — физики, алгебре, геометрии и т. п.).