Автор работы: Пользователь скрыл имя, 22 Марта 2014 в 17:01, контрольная работа
Первое из этих направлений связано с построением формальной, или математической, лингвистики, которая начала особенно быстро развиваться в тот период, когда были сформулированы вопросы машинного перевода. Эта проблема требовала формализации понятий словарь, грамматика, язык, их классификации и умения относить конкретные словари, грамматики, языки к определенному классу.
1. Теоретическая часть……………………………………………………..3
1.1. Введение………………………………………………………………...3
1.2. Основные понятия порождающих грамматик…………………… 5
1.3. Классификация грамматик………………………………………….7
1.4. Грамматический разбор……………………………………………...8
1.5. Преобразование КС-грамматик……………………………………. 9
2. Практическая часть……………………………………………………14
2.1 Задание 1: Расчет информационной емкости документов предметной области……………………………………………………..14
2.2 Задание 2: Построение инфологической и моделей предметной области……………………………………………………………………16
2.3 Задание 3: Формирование информационных запросов к реляционной базе данных с помощью операций реляционной алгебры…………………………………………………………………...19
2.4 Задание 4: Применение поиска и сортировки данных…………….21
3. Список используемой литературы…………………………………...24
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ
по дисциплине «Теоретические основы информатики»
Специальность:
Группа: 1б-иу100
№ зачетной книжки: 100.16/120332
Руководитель:
Оглавление
Введение.
В последние три десятилетия появилось большое количество работ по общей теории языков и грамматик. Можно выделить четыре научных направления, которые удалось объединить по методам их исследования в одну общую задачу теории языков.
Первое из этих направлений связано с построением формальной, или математической, лингвистики, которая начала особенно быстро развиваться в тот период, когда были сформулированы вопросы машинного перевода. Эта проблема требовала формализации понятий словарь, грамматика, язык, их классификации и умения относить конкретные словари, грамматики, языки к определенному классу.
Интерес к задачам такого рода еще более усилился с появлением искусственных языков программирования. С появлением трансляторов проблема перевода во многом определила построение общей теории вычислительных машин, а сами языки программирования стали
все более приближаться к формально построенным математическим конструкциям.
Независимо от указанных двух направлений развивалось построение формальных моделей динамических систем. Для создания продуктивной теории эти модели должны были быть, с одной стороны, достаточно узкими, а с другой - достаточно широкими, чтобы охватить некоторый общий класс прикладных задач. Типичным примером такого рода является модель конечного автомата. Эта модель позволяет описать многие процессы,
заданные на конечных множествах и развивающиеся в счетном времени, что позволило создать для нее продуктивную теорию. Если в эту модель ввести бесконечность по какому- либо параметру, то это приводит к общему классу систем, например, к машинам Тьюринга.
Независимо и параллельно развивалась общая теория алгоритмов как ветвь современной математики. Развитие вычислительной техники поставило перед математической теорией алгоритмов новую задачу: стало необходимым классифицировать алгоритмы по различным
признакам. Эквивалентность понятий "алгоритм" и "машина Тьюринга" позволила предположить, что поиски классификации алгоритмов окажутся связанными с поисками промежуточных моделей между моделями конечного автомата и машиной Тьюринга.
Таким образом, перечисленные четыре направления оказались тесно связанными. Теория языков, порожденная чисто лингвистическими задачами, оказалась в центре интересов математиков, занимающихся теорией алгоритмов, и ученых, разрабатывающих абстрактные модели динамических систем и теоретические основы автоматики.
Теория формальных языков и грамматик является разделом математической
лингвистики - специфической математической дисциплины, ориентированной на изучение структуры естественных и искусственных языков. По характеру используемого математического аппарата теория формальных грамматик и языков близка к теории алгоритмов и теории автоматов.
На интуитивном уровне язык можно определить как некоторое множество предложений с заданной структурой, имеющих определенное значение. Правила, определяющие допустимые конструкции языка, составляют синтаксис языка. Значение, или смысл фразы, определяется семантикой языка. Если бы все языки состояли из конечного числа предложений, то не было бы проблемы синтаксиса. Но, так как язык содержит неограниченное (или довольно большое) число правильно построенных фраз, то возникает проблема описания бесконечных языков с помощью каких-либо конечных средств.
Различают следующие виды описания языков:
1) порождающее, которое предполагает наличие алгоритма, последовательно
порождающего все правильные предложения языка;
2) распознающее, которое
предполагает наличие
принадлежность любой фразы данному языку
Основные понятия порождающих грамматик
Алфавит - это непустое конечное множество. Элементы алфавита называются символами.
Цепочка над алфавитом Σ={а1, а2, …, аn} есть конечная оследовательность элементов аi. Множество всех цепочек над алфавитом Σ обозначается ~_è¯l__†ïþΣ*.
Длина цепочки х равна числу ее элементов и обозначается |x|. Цепочка нулевой длины называется пустой и обозначается символом ε. Соответственно, непустая цепочка определяется как цепочка ненулевой длины. Пусть имеется алфавит Σ={а, b}. Тогда множество всех цепочек определяется следующим образом: Σ*={ ε, а, b, aa, ab, ba, bb, aaa,
aab, aba, . . .}.
Цепочки x и y равны, если они одинаковой длины и совпадают с точностью до порядка символов, из которых они состоят.
Над цепочками x и y определена операция сцепления (конкатенации, произведения), которая получается дописыванием символов цепочки y за символами цепочки x.
Язык L над алфавитом Σ представляет собой множество цепочек над Σ. Необходимо различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={ε}≠0.
Формальный язык L над алфавитом Σ - это язык, выделенный с помощью конечного множества некоторых формальных правил.
Порождающая грамматика - это упорядоченная четверка G= (Vт, VN, P, S), где VТ - конечный алфавит, определяющий множество терминальных символов;
VN - конечный алфавит, определяющий множество нетерминальных символов;
Р - конечное множество правил вывода, т.е. множество пар следующего вида:
u → v, где u, v ∈(VТ∪VN)*;
S - начальный символ (аксиома грамматики), S∈VN.
Из терминальных символов состоят цепочки языка, порожденного грамматикой. Аксиомой называется символ в левой части первого правила вывода грамматики.
Для того чтобы различать терминальные и нетерминальные символы, принято обозначать терминальные символы строчными, а нетерминальные символы заглавными буквами латинского алфавита.
В грамматике G цепочка х непосредственно порождает цепочку у, если х = αuβ, у = αvβ и u→v ∈ Р, т.е. цепочка у непосредственно выводится из х, что обозначается х => у.
Языком, порождаемым грамматикой G = (VТ, VN, Р, S), называется множество терминальных цепочек, выводимых в грамматике G из аксиомы:
L(G) = {х | х ∈ VТ*; S => *х}, где =>*- выводимость.
Пример. Дана грамматика G = (VТ, VN, Р, S), в которой Vт = {а, b}, VN = {S}, Р = {S → aSb, S → ab). Определить язык, порождаемый этой грамматикой.
Решение. Используя рекурсию, выведем несколько цепочек языка, порождаемого данной грамматикой:
S → ab;
S → aSb => aabb;
S → aSb =>aaSbb => aaabbb; . . .
Определим язык, порожденный данной грамматикой:
L(G) = {aⁿbⁿ | n > 0}.
Говоря о представлении грамматик, нужно отметить, что множество правил вывода грамматики может приводиться без специального указания множеств терминалов и нетерминалов. В таком случае обычно предполагается, что грамматика содержит в точности те терминальные и нетерминальные символы, которые встречаются в правилах вывода.
Также предполагается, что правые части правил, для которых совпадают левые части, можно записать в одну строку с использованием разделителя. Так, правила вывода из приведенного примера можно записать следующим образом: S → aSb | ab.
Классификация грамматик
Правила порождающих грамматик позволяют осуществлять преобразования строк. Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотрим классификацию, которую предложил Н. Хомский.
Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений.
Грамматики типа 1, или контекcтные грамматики -это грамматики, все правила которых имеют следующий вид: хАу → хϕу, где A ∈ Vn, x, y, ϕ ∈ (VN ∪ Vт)+.
Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КС-грамматики). Правила вывода для этих грамматик имеют следующий вид: А → ϕ, где А ∈ VN, ϕ ∈ (VN ∪ Vт)*.
Грамматики типа 3 - это автоматные грамматики, которые делятся на два типа:
а) леволинейные (леворекурсивные), правила вывода для которых имеют следующий вид: А → Аа | a, где А ∈ VN;
б) праволинейные (праворекурсивные), правила вывода для которых имеют следующий вид: А → Aа | a.
Язык L называется языком типа i, если существует грамматика типа i, порождающая язык L.
Пример 1. Дана порождающая грамматика G = (VТ, VN, Р, S), в которой Vт = {a, d, е}, VN = {В, С, S}, Р = {S → аВ, В → Cd | dC, С → е}. Выписать терминальные цепочки, порожденные данной грамматикой, и определить длину их вывода.
Решение. Получим следующие терминальные цепочки:
S → аВ → aCd → aed,
S → аВ → adC → ade,
длина вывода которых равна 3.
Пример 2. Дана грамматика G = (Vт, VN, Р, C), в которой Vт = {a, b, c, d, е}, VN = {A, В, С, D, E}, Р = {A → ed, В → Ab, С → Bc, С → dD, D → Ae, E → bc}. Определить, принадлежит ли языку L(G) цепочка eadabcb.
Решение. Выведем возможные терминальные цепочки из аксиомы с помощью заданных правил вывода:
С → Bc → Abc → edbc,
С → dD → dAe → dede.
Так как первые же терминальные символы полученных цепочек не совпадают с заданной, можно сделать вывод о том, что цепочка eadabcb не принадлежит языку L(G).
Грамматический разбор
В КС-грамматике может быть несколько выводов, эквивалентных в том смысле, что в
них применяются одни и те же правила к одинаковым в промежуточном выводе цепочкам,
но в различном порядке. Например, для грамматики G с правилами вывода S → ScS|b|a
возможны следующие эквивалентные выводы терминальной цепочки acb: S → ScS →
Scb → acb и S → ScS → acS → acb.
Деревом вывода цепочки х в КС-грамматике G = (VТ, VN, Р, S) называется
упорядоченное дерево, каждая вершина которого помечена символом из множества
V ∪ VN ∪ {ε} так, что каждому правилу А → b1b2b3 ... bk, использующемуся при выводе цепочки х, в дереве вывода соответствует поддерево с корнем А и прямыми потомками b1, b2, b3, ..., bk, которое приведено на рисунке:
A