47) Понятие о математической лингвистике. Формальный язык. Кодирование цепочек.

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

Язык может быть описан математическими средствами, как преобразование некоторых абстрактных объектов – смыслов, в некоторые объекты – тексты и обратно:

1,Переход от смыслов к синтаксическим структурам без линейного порядка.

2,Переход к линейным последовательностям слов.

3,Получение цепочек звуков.

знаковые системы, в которых знаками являются символы алфавитов, а последовательностями знаков – тексты. Задается алфавит ={a,b,c,….x,y,z}, состоящий из букв или символов Слово ω  называется еще цепочкой ω. Длина цепочки обозначается | ω | .

При k =0 получаем пустое слово, обозначаемое . | | =0.

- множество всех слов – эквивалент универсума теории множеств.

Над цепочками вводятся операции

-конкатенации -итерации  (сцепления*(повторения), -инверсии (реверса), циклического сдвига перестановка групп символов

- замена одной подцепочки данной цепочки другой цепочкой

Формальный язык в алфавите - это некоторое подмножество: .

Определение языков – это их задание. Оно осуществляется следующими способами:

-перечислением всех правильных цепочек языка;

-порождением всевозможных цепочек и их «фильтрацией» с

-помощью так называемых распознавателей, которые распознают требуемые цепочки;

- заданием соответствующей грамматики.

48) Формальные грамматики и их св-ва

Формальная грамматика – формальная система, исчисление.

Различают, распознающие, порождающие и преобразующие формальные грамматики.

Формальная грамматика называется распознающей, если для любой рассматриваемой цепочки она решает, является ли эта цепочка правильной в смысле данной грамматики.

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

Формальная грамматика называется преобразующей, если для любой правильно построенной цепочки она строит её отображение в виде правильной цепочки.

Грамматика типа 0 – это грамматики, в которых не накладывается никаких ограничений на правила вывода jy, где j и yмогут быть любыми цепочками из V.

Грамматики типа 3 имеют правила вида А aB, либо Ab, где А,ВÎN; a,bÎT.Здесь A,B,a,b- одиночные символы (не цепочки) соответствующих словарей. Языки, которые задаются грамматиками этого типа называются автоматными или регулярными.

b. Грамматики типа 1 называю контекстными или контекстно-зависимыми.

Грамматика типа 2- это грамматики, в которых допустимы лишь правила вида Аa, где aÎТ È N, т.е. a - непустая цепочка из V. Грамматика типа 2 называют бесконтекстными или контекстно-свободными.

Грамматика типа 1 – это грамматика, все правила которой имеют вид aАbawb, где wÎТ È N, А - нетерминальный символ. Цепочки a и b - контекст правил. Они не изменяются при его применении.

49) Автоматное представление регулярных языков