Алгоритмические основы вычислительных процессов. Элементы теории алгоритмов и формальных языков

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДАРЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«ВСЕРОССИЙСКИЙ  ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ»

Кафедра прикладной информатики

 

КОНТРОЛЬНАЯ РАБОТА

 

по дисциплине «Теоретические основы информатики»

на тему

«Алгоритмические основы вычислительных процессов.

Элементы  теории алгоритмов и формальных языков»

Вариант 12

 

 

                                                                            Исполнитель: Кичигина А.С.

                                                                           Специальность: Бизнес-информатика

                                                                            Факультет: Учетно-статистический

                                                                            Курс 1

                                                                           № зачетной книжки: 100.13/120072

                                                                          Руководитель: Зиновьева Л.В.

 

Краснодар 2012

 

 

Оглавление:

 

1.Введение......................................................................................................3

 

 

1.1Теоретическая часть................................................................................4

 

 

1.2-Содержание.............................................................................................4

 

 

1.3-Заключение..............................................................................................11

 

 

2. Практическая часть....................................................................................12

 

3. Список использованной литературы.......................................................16

 

 

 

 

Введение

 

Тема: Алгоритмические основы вычислительных процессов.

Элементы теории алгоритмов и формальных языков

Вопрос №12. Формальные языки и порождающие  грамматики.

Цель:

 разобрать : формальный язык и его применение в области информатики, а так же формальная грамматика и ее порождающие

 

 

Теоретическая часть

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

В теории моделей язык соответствует  не языку в информатике, а скорее алфавиту. Язык состоит из множеств символов, функций и отношений  вместе с их арностью( А́рность предиката, операции или функции в математике — количество их аргументов, или операндов. Слово образовалось из названий предикатов небольшой арности (унарный — один аргумент, бинарный — два, тернарный — три). Также для этих целей употребляется термин валентность. В общем случае предикат с аргументами называют -арным. Также употребляются термины местность (-местный) и, соответственно, вместимость   , а также множество переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.

 

Определение

Формальный язык может быть определён  по-разному, например:

-Простым перечислением слов, входящих в данный язык. (Этот способ, в основном, применим для определения конечных языков и языков простой структуры.)

-Словами, порождёнными некоторой формальной грамматикой

-Словами, порождёнными регулярным выражением.

-Словами, распознаваемыми некоторым конечным автоматом.

-Словами, порождёнными БНФ-конструкцией.

Если алфавит задан как {a, b}, а язык L включает в себя все слова над ним, то слово ababba принадлежит L. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, ε или Λ.

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

множество всех слов над {a, b}

множество , где n — неотрицательное число, а означает, что a повторяется n раз

множество синтаксически корректных программ в данном языке программирования

 

Операции

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

-Конкатенация (сцепление.

-Пересечение  

-Объединение  

-Дополнение.

-Правое 

-Замыкание Клини  

-Обращение  

Другие значения

 

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

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

 

Формальная грамматика

Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие  и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить  любое слово языка, а вторые позволяют  по данному слову определить, входит оно в язык или нет.

 

Термины

-Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.

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

 

Порождающие грамматики

Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.

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

Итак, грамматика определяется следующими характеристиками:

 ∑— набор (алфавит) терминальных символов

N — набор (алфавит) нетерминальных  символов

P — набор правил вида: «левая  часть»  «правая часть», где:

        «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал

       «правая часть» — любая последовательность терминалов и нетерминалов

S — стартовый (начальный) символ  из набора нетерминалов.

Вывод

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

Существование вывода для некоторого слова является критерием его  принадлежности к языку, определяемому  данной грамматикой.

 

Типы грамматик

По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий  является более ограниченным подмножеством  предыдущего (но и легче поддающимся  анализу):

-тип 0. неограниченные грамматики(формальные грамматики типа 0 по иерархии Хомского (в отличие от более определённых и ограниченных типов).

Этот класс грамматик представляет теоретический интерес, но практически  не применяется как таковой. — возможны любые правила

-тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.

-тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.

-тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.

 

Применение

Контекстно-свободные грамматики широко применяются для определения  грамматической структуры в грамматическом анализе.Регулярные грамматики (в виде регулярных выражений) широко применяются как шаблоны для текстового поиска, разбивки и подстановки, в том числе в лексическом анализе.

Пример — арифметические выражения

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

Терминальный алфавит:={0,1,2,3,4,5,6,7,8,9,0,+,-,*,/}.

Нетерминальный алфавит:  { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

Правила:

1. ФОРМУЛА=  ФОРМУЛА ,ЗНАК,  ФОРМУЛА  (формула есть две формулы, соединенные знаком)

2. ФОРМУЛА  =ЧИСЛО      (формула есть число)

3. ФОРМУЛА = ( ФОРМУЛА )    (формула есть формула в скобках)

4. ЗНАК   + ,  - ,  * ,  /  (знак есть плюс или минус или умножить или разделить)

5. ЧИСЛО=  ЦИФРА (число есть цифра)

6. ЧИСЛО = ЧИСЛО ,ЦИФРА   (число есть число и цифра)

7. ЦИФРА  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра  есть 0 или 1 или ... 9 )

Начальный нетерминал: ФОРМУЛА

Аналитические грамматики

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

Так же можно рассмотреть:

Синтаксический  анализ- В информатике, синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом. Синтаксический анализатор (парсер) — это программа или часть программы, выполняющая синтаксический анализ.

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

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

Область применения

Всё что угодно, имеющее «синтаксис», поддается автоматическому анализу.

-Языки программирования — разбор исходного кода языков программирования, в процессе трансляции (компиляции или интерпретации).

-Структурированные данные — данные, языки их описания, оформления и т. д. Например, XML, HTML, CSS, ini-файлы, специализированные конфигурационные файлы и т. п.

-SQL-запросы (DSL-язык)

-математические выражения

-регулярные выражения (которые, в свою очередь, могут использоваться для автоматизации лексического анализа)

-формальные грамматики

-Лингвистика — человеческие языки. Например, машинный перевод и другие генераторы текстов.

Типы алгоритмов

-Нисходящий парсер (англ. top-down parser) — продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.

             -LL-анализатор

-Восходящий парсер (англ. bottom-up parser) — продукции восстанавливаются из правых частей, начиная с токенов и кончая стартовым символом.

            -LR-анализатор

             -GLR-парсер

 

 

 

 

 

Таким  образом, мы выяснили , что  Формальный язык — это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков, а Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

Так же мы выяснили их области применения, типы, характеристики. А так же узнали характерные определения для  этой темы, такие как :

- Структурированные данные

- Языки программирования

- Нетерминал (нетерминальный символ)

- Формальный язык

- Формальная грамматика

- Порождающие грамматики и многие другие.

 

 

Практическая часть :

В предметной области " Учет кадров" обрабатывается информация о кадровом составе некоторого предприятия . Данные о каждом работнике  фиксируются  в личном листке  по учету кадров, в котором также фиксируются  данные о внутреннем  перемещении  работника  на данном  предприятии . Должностные оклады работников  определяются штатным расписанием.

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