Общие сведения. В последние три десятилетия появилось большое количество работ по общей теории языков и грамматик

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

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

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

Независимо от указанных двух направлений развивалось построение формальных моделей динамических систем. Для создания продуктивной теории эти модели должны были быть, с одной стороны, достаточно узкими, а с другой - достаточно широкими, чтобы охватить некоторый общий класс прикладных задач. Типичным примером такого рода является модель конечного автомата. Эта модель позволяет описать многие процессы, заданные на конечных множествах и развивающиеся в счетном времени, что позволило создать для нее продуктивную теорию. Если в эту модель ввести бесконечность по какому- либо параметру, то это приводит к общему классу систем, например, к машинам Тьюринга.

Независимо и параллельно развивалась общая теория алгоритмов как ветвь современной математики. Развитие вычислительной техники поставило перед математической теорией алгоритмов новую задачу: стало необходимым классифицировать алгоритмы по различным признакам. Эквивалентность понятий "алгоритм" и "машина Тьюринга" позволила предположить, что поиски классификации алгоритмов окажутся связанными с поисками промежуточных моделей между моделями конечного автомата и машиной Тьюринга.

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

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

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

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

Различают следующие виды описания языков:

1) порождающее, которое предполагает наличие алгоритма, последовательно порождающего все правильные предложения языка;

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

Основные понятия порождающих грамматик

Алфавит - это непустое конечное множество. Элементы алфавита называются символами.

Цепочка над алфавитом Σ={а₁, а₂, …, а_n} есть конечная последовательность элементов аi. Множество всех цепочек над алфавитом Σ обозначается __________Σ*.

Длина цепочки х равна числу ее элементов и обозначается |x|. Цепочка нулевой длины называется пустой и обозначается символом ε. Соответственно, непустая цепочка определяется как цепочка ненулевой длины. Пусть имеется алфавит Σ={а, b}. Тогда множество всех цепочек определяется следующим образом: Σ*={ ε, а, b, aa, ab, ba, bb, aaa, aab, aba, . . .}.

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

Над цепочками x и y определена операция сцепления (конкатенации, произведения), которая получается дописыванием символов цепочки y за символами цепочки x. Язык L над алфавитом Σ представляет собой множество цепочек над Σ. Необходимо различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={ε}≠0.

Формальный язык L над алфавитом Σ - это язык, выделенный с помощью конечного множества некоторых формальных правил.

Пусть M и L - языки над алфавитами. Тогда конкатенация LM = {xyx∈L, y∈M}. В частности, {ε}L = L{ε}=L. Используя понятие произведения, определим итерацию L* и усеченную итерацию L+ множества L:

L⁺ =

L^* =

где i - степень языка, L определяется рекурсивно следующим образом:

L⁰ = {ε};

L¹ = L;

Lⁿ⁺¹ = Lⁿ L = L Lⁿ;

{ε}L=L{ε}=L.

Например, если задан язык L={a}, тогда L^*={ε, а, аа, ааа, …}, L⁺={a, aa, aaa, …}.

Порождающая грамматика - это упорядоченная четверка G= (V_T, V_N, P, S), где V_T - конечный алфавит, определяющий множество терминальных символов;

V_N - конечный алфавит, определяющий множество нетерминальных символов;

Р - конечное множество правил вывода, т.е. множество пар следующего вида:

u → v, где u, v Î(V_TÈV_N)*;

S - начальный символ (аксиома грамматики), SÎV_N.

Из терминальных символов состоят цепочки языка, порожденного грамматикой.

Аксиомой называется символ в левой части первого правила вывода грамматики.

Для того чтобы различать терминальные и нетерминальные символы, принято обозначать терминальные символы строчными, а нетерминальные символы заглавными буквами латинского алфавита.

В грамматике G цепочка х непосредственно порождает цепочку у, если х = αuβ, у = αvβ и u→v Î Р, т.е. цепочка у непосредственно выводится из х, что обозначается х => у.

Языком, порождаемым грамматикой G = (VT, VN, Р, S), называется множество терминальных цепочек, выводимых в грамматике G из аксиомы:

L(G) = {х | хÎV_T*; S => *х}, где =>*- выводимость.

Пример. Дана грамматика G = (V_T, V_N, Р, S), в которой VT = {а, b}, V_N = {S}, Р = {S → aSb, S → ab). Определить язык, порождаемый этой грамматикой.

Решение. Используя рекурсию, выведем несколько цепочек языка, порождаемого данной грамматикой:

S → ab;

S → aSb => aabb;

S → aSb =>aaSbb => aaabbb; . . .

Определим язык, порожденный данной грамматикой:

L(G) = {aⁿbⁿ | n > 0}.

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

Также предполагается, что правые части правил, для которых совпадают левые части, можно записать в одну строку с использованием разделителя. Так, правила вывода из приведенного примера можно записать следующим образом: S → aSb | ab.

Дата добавления: 2015-07-26; просмотров: 182; Нарушение авторских прав

Мы поможем в написании ваших работ!