Основные понятия теории формальных языков

В основе каждого языка лежит алфавит.

Определение Алфавитом V называется конечное множество символов.

Определение Цепочкой a в алфавите V называется любая конечная последовательность символов этого алфавита.

Определение Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается e.

Определение Формальное определение цепочки символов в алфавите V:

1) e - цепочка в алфавите V;

2) если a - цепочка в алфавите V и а – символ этого алфавита, то a а – цепочка в алфавите V;

3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу утверждений 1) и 2).

Определение Длиной цепочки a называется число составляющих ее символов (обозначается |a|).

Определение Конкатенацией (сцеплением) цепочек a и b называется цепочка g = ab, в которой символы данных цепочек записаны друг за другом.

Для любой цепочки a справедливо утверждение ae = ea.

Определение Степенью n цепочки a называется конкатенация n цепочек a. (обозначается aⁿ).

Для любой цепочки a справедливы утверждения a ⁰= e и aⁿ = a^{n -1} a = aa^{n -1} для n ³1.

Определение Реверсом (обращением) цепочки a называется цепочка a^R, составленная из символов цепочки a, записанных в обратном порядке.

Пример Пусть алфавит V ={ a, b, c, d }, тогда для цепочек этого алфавита a = ab и b = bcd будет справедливо |a|= 2, |b|= 3, ab = abbcd, a² = abab, b^R = dcb.

Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e, а через V⁺ - множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e.

Определение Формальным языком L в алфавите V называют произвольное подмножество множества V ^*.

Пример Пусть алфавит двоичных цифр , тогда , а .

Задать язык L в алфавите V можно тремя способами:

1) перечислением всех допустимых цепочек языка (на языке множеств);

2) указанием способа порождения (генерации) цепочек языка (грамматики, формы Бэкуса-Наура и диаграммы Вирта;

3) определением метода распознавания цепочек языка (распознаватели).

Пример Язык L в алфавите , состоящий из пустой строки и всевозможных строк, каждая из которых содержит строку нулей и последующую строку единиц той же длины, можно описать с помощью формальной системы определения множеств как L= {0 ⁿ 1 ⁿ | n³ 0}.