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

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ

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

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

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

 

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

 

КУРСОВАЯ РАБОТА

 

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

 

на тему

«Формальные языки и порождающие грамматики»

 

Вариант №12

 

 

Исполнитель:

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

Группа:

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

Руководитель:

 

 

 

 

 

 

 

 

Калуга

2011

 

Оглавление:

 

 

Теоретическая часть…………………………………………………………..3-11

Введение…………………………………………………………………………………3

Естественные  и формальные языки………………………………………………4-5

Возникновение формального языка………………………………………………..6

Схема построения формального языка…………………………………………..7

Понятие грамматики. Формальная грамматика……………………………...8-9

Пример порождающей грамматики…………………………………………..10-11

Заключение…………………………………………………………………………….12

Практическая  часть…………………………………………………………..13-32

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

 

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

(Формальные языки и  порождающие грамматики)

 

Введение.

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

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

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

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

Но независимо от формы представления и способа передачи информации, она всегда передается с помощью какого-либо языка.

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

 

Естественные и формальные языки.

 

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

 

В процессе развития человеческого общества люди выработали большое число языков.

• разговорные языки (в настоящее время в мире их насчитывают более 2000);
• языки мимики и жестов;
• языки чертежей, рисунков, схем;
• языки науки (математики, химии, биологии и т.д.);
• языки искусства (живописи, музыки, скульптуры, архитектуры и т.д.);
• специальные языки (азбука Брайля для слепых, азбука Морзе, Эсперанто, морской семафор и т.д.);
• алгоритмические языки (блок-схемы, языки программирования).

 

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

 

Язык характеризуется:

• набором используемых знаков;
• правилами образования из этих знаков таких языковых конструкций, как “слова”, “фразы” и “тексты” (в широком толковании этих понятий);
• набором синтаксических, семантических и прагматических правил использования этих языковых конструкций.

 

Основу языка  составляют:

• Алфавит(словарь) - конечное множество символов, неделимых в данном рассмотрении, символы, входящие в множество называются буквами алфавита

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

слово  - последовательность символов алфавита, кодирующая информацию;

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

 

 

Естественными называются “обычные”, “разговорные” языки, которые складываются стихийно и в течение долгого времени. История каждого такого языка неотделима от истории народа, владеющего им. Естественный язык, предназначенный, прежде всего, для повседневного общения

 

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

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

 

 

 

Возникновение формального языка.

Возникновение языков программирования приходится на начало 50-х годов XX века.

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

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

 

 

 

 

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

Особое место  среди языков программирования занимают языки, обеспечивающие работу систем управления базами данных (СУБД). Часто в них  выделяют две подсистемы: язык описания данных и язык манипулирования.

 

 

Схема построения формального языка

Большинство формальных языков (созданных конструкций) строится по следующей схеме. сначала  выбирается алфавит, или совокупность исходных символов, из которых будут  строиться все выражения языка; затем описывается синтаксис  языка, то есть правила построения осмысленных  выражений. Буквами в алфавите формального  языка могут быть и буквы алфавитов  естественных языков, и скобки, и  специальные знаки и т.п. Из букв, по определенным правилам можно составлять слова и выражения. Осмысленные  выражения получаются в формальном языке, только если соблюдены определенные в языке правила образования. Для каждого формального языка  совокупность этих правил должна быть строго определена и модификация  любого из них приводит чаще всего  к появлению новой разновидности (диалекта) этого языка.

 

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

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

 

 

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

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

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

 

Формальной порождающей  грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт, VA, <I> О VA, R },

где

Vт - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки порождаемые грамматикой;

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

<I> - начальный символ грамматики <I> О VA.

R - множество правил вывода или порождающих правил вида a ® b , где aи b - цепочки ,

построенные из букв алфавита VтИ VA, который называют полным алфавитом (словарем) грамматики Г

 

 

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

Примером языка может являться множество различных корректных формул, включающих в себя натуральные  числа, скобки и знаки арифметических действий. Алфавитом в этом случае будет множество Σ={'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}. Например, строка (2+3)*(5+7) будет словом такого языка, а строка +2(3-1( не будет (хотя она и состоит из допустимых символов, но записана с очевидными ошибками). Как можно описать этот язык? Мы знаем, что числа состоят из цифр и могут объединяться с помощью знаков арифметических действий в формулы (например, формулой будет цепочка 2+3). Формулы можно заключать в скобки, а также складывать, вычитать, умножать и делить — то есть объединять друг с другом (и с числами) в более сложные формулы. Например, (2+3)*(5+7) — это сложная формула, состоящая из двух более простых, ее можно символически записать следующим образом: ФОРМУЛА ЗНАК ФОРМУЛА. Заметим, что вместо слов ФОРМУЛА можно подставить любую корректную формулу, а вместо слова ЗНАК — знак любого арифметического действия, и эта строка останется правильной формулой.

Идея теории порождающих формальных грамматик, разработанной Н.Хомским, состоит в том, чтобы описывать язык через правила подстановок, которые позволяют строить слова языка из «кирпичиков», описываемых с помощью других «кирпичиков». Правила языка при этом можно записывать, просто указывая, какие цепочки «кирпичиков» можно подставлять вместо других «кирпичиков». Например, разобранное выше правило построения сложных формул из простых можно записать следующим образом (такая запись называется правилом вывода)

1. ФОРМУЛА   ФОРМУЛА ЗНАК ФОРМУЛА

Правило нужно читать так: «вместо слова ФОРМУЛА можно подставить цепочку ФОРМУЛА ЗНАК ФОРМУЛА». При этом вместо «кирпичика» ЗНАК можно подставлять один из четырех символов алфавита Σ: (+,-,*./). Это можно записать с помощью следующих четырех правил:

2. ЗНАК   +

3. ЗНАК   -

4. ЗНАК   *

5. ЗНАК   /

Такая запись обычно сокращается до следующей (символ "|" не принадлежит Σ).

6. ЗНАК   + | - | * | /

«Кирпичики», обозначаемые нами большими буквами (например, ЗНАК), не являются символами рабочего алфавита Σ (хотя и могут быть на них заменены в процессе подстановок). Они называются «нетерминалами» (или «нетерминальными символами»), в отличие от букв алфавита Σ, называющихся терминалами. Смысл этих названий состоит в том, что нетерминал может быть заменен на цепочку других символов (как в случае с нетерминалом ФОРМУЛА), в то время как терминал уже ни на что заменен быть не может и является своеобразным «пунктном назначения» наших замен (от англ. terminal — конечный пункт). Чтобы получить слово языка, мы должны все нетерминалы в конечном итоге заменить на терминалы, а для этого в описание языка должны входить соответствующие правила.

В рассмотренном примере для  определения нетерминала ЧИСЛО можно ввести такие правила:

7. ЧИСЛО   ЦИФРА | ЧИСЛО ЦИФРА

8. ЦИФРА   0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

 

Иными словами, если к числу приписать  справа еще одну цифру, то получится  снова число. Одно число — это также корректная формула, что записывается следующим образом:

9. ФОРМУЛА   ЧИСЛО

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

10. ФОРМУЛА   ( ФОРМУЛА )

Надо отметить, что нетерминал ФОРМУЛА в нашем случае является выделенным — он задает правильные формулы, то есть слова нашего языка, в то время как, например, нетерминал ЗНАК не задает слово языка. В таком случае говорят, что нетерминал ФОРМУЛА является начальным.

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

 

Заключение.

 

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

 

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

 

Задание 1

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