Формальные грамматики. Типы формальных грамматик.

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

Существует два типа формальных грамматик:

1. Грамматики порождающие - система правил, позволяющая строить предложение языка.

2. Грамматики распознающие – алгоритмы, распознающие по любой цепочке символов, является ли эта цепочка предложением.

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

Среди порождающих формальных грамматик различают:

1. Составляющая грамматика

2. Безконтекстная грамматика

3. Автоматная грамматика.

Тема9: Основной метод информатики.

Основной метод информатики можно представить в виде следующей схемы:

1. Предметная область (построение информационной модели)

2. Естественный язык (построение концептуальной модели)

3. Формальный язык (построение логической модели)

4. Построение алгоритма

5. Разработка программы

1. Предметная область

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

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

2. Концептуальная модель

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

3. Логическая модель

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

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

Схема эквивалентной интерпретации.

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

Абстрактное состояние – есть множество абстрактных объектов E, множество типов T, множество отношений R. Тогда процесс интерпретации описания состояния предметной области на естественном языке означает следующее соответствие:

1. соответствие фраз, однозначно именующих реальные объекты с различными абстрактными объектами из множества E.

2. соответствие фраз, обозначающих свойства объектов с типами из множества T.

3. соответствие фраз, обозначающих взаимоотношения конкретных объектов с кортежами отношения c R.

Рассмотрим жизненный пример:

Группа ИС-103 пишет самостоятельную работу №2 по лекции №4.

1. Дадим описание на естественном языке:

Группа №103 есть группа с названием ИС и номером группы 103.

Самостоятельная работа С-2 есть самостоятельная работа с шифром С-2.

Ресурс Л-4 есть лекция с шифром Л-4.

Группа ИС-103 пишет самостоятельную работу С-2. Самостоятельная работа С-2 потребляет ресурс Л-4.

2. Интерпретируем данное описание при помощи абстрактных состояний, т.е. используя множество {E, T, R}.

Абстрактные объекты E={l1,l2,…,ln}, n=7

L1 – группа №103

L2 - №103

L3 – ИС

L4 – Самостоятельная работа С-2

L5 – С-2

L6 – лекция Л-4

L7 – Л-4.

Свойства абстрактных объектов: T={t1,t2,…,tn}, n=7

T1 – быть группой

T2 – быть номером группы

T3 - быть названием группы

T4 – быть самостоятельной работой

T5 – быть шифром самостоятельной работы

T6 – быть ресурсом

T7 – быть шифром ресурса

Отношения между абстрактными объектами представляются множеством R={R1, R2, ..,Rn}

R1 – группа имеет номер = {l1,l2}

R2 – группа имеет название = {l1,l3}

R3 – группа пишет самостоятельную работу = {l1,l4}

R4 – самостоятельная работа имеет шифр = {l4,l5} и т.д.

Таким образом мы получили описание предметной области на естественном языке путем интерпретации через абстрактные состояния.

Перечислим основные принципы описания состояния предметной области на некотором формальном языке:

1. Раскрытие содержания при помощи описания предметной области на естественном языке, позволяющим соотносить элементы описания с реальными объектами.

2. установление факта эквивалентности описаний на различных языках с помощью абстрактной интерпретации

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