Формализованные (формальные) языки

8

ФОРМАЛИЗОВАННЫЕ (ФОРМАЛЬНЫЕ) ЯЗЫКИ

ПОНЯТЬ

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

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

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

Формальные языки часто конструируются на базе языка математики.

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

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

Все формальные языки - это кем-то созданные конструкции. Большинство из них строятся по следующей схеме.

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

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

Из букв, по определенным правилам можно составлять слова и выражения.

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

ПРИМЕР 1

Одним из важных с точки зрения информатики является алфавит, состоящий из двух букв “0”, “1”. Всякой конечная последовательность нулей и единиц - есть слово в этом алфавите.

В логико-математических языках среди выражений различают термы и формулы.

Термы - это аналог имен объектов, их основное назначение - обозначать некоторый объект.

К термам прежде всего относятся предметные переменные и константы - выражения, служащие для обозначения конкретных объектов.

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

ПРИМЕР 2

В логике такими функциями являются инверсия (), конъюнкция (), дизъюнкция (), импликация () и др.

Примеры термов в алгебре логики:

А; АВ А; (АС).

В языках программирования в образовании термов участвуют арифметические операции, операции отношения (,

Примеры термов в языке программирования Pascal:

А; prog_1; ((A1+25)3*B) and (B0)); 2+sqrt(z*sin(b)).

Формулы образуются из термов, к которым применены допустимые в языке операторы.

ПРИМЕР 3

Примеры логических формул:

(АС)  АС = 1; x((x)(x))

Формулами в языке программирования можно назвать операторы программы.

Примеры “формул” языка программирования Pascal:

A:= 2+sqrt(Z*sin(B)); if F3 then write(R) else R:=sqr(F);

Осмысленные выражения получаются в формальном языке, только если соблюдены определенные в языке правила образования, преобразования и “понимания” термов и формул. К таким правилам относятся:

1. правила построения термов и формул;

2. правила интерпретации термов и формул (семантический аспект языка);

3. правила вывода одних формул и термов из других формул и термов.

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

ПРИМЕР 4

Оператор языка Pascal

if F3 then write(R) else R:=sqr(F);

интерпретируется в соответствии со следующим правилами:

• переменная F может быть только целого или вещественного типа, а переменная R - только вещественного типа. Если это не так, то считается, что оператор синтаксически неверен, и выполняться он не будет (будет выдано сообщение о синтаксической ошибке);

• переменные (простейшие термы) F и R, должны быть ранее определены, то есть ячейки с этими именами должны содержать какие-то значения соответствующего типа (для некоторых версий Pascal это правило не входит в синтаксис языка. В этом случае выбирается та последовательность нулей и единиц, которая содержится в ячейках с заданными адресами и интерпретируется как десятичное число);

• если значение выражения (сложного терма “F3”), стоящего вслед за ключевым (зарезервированным) словом if, есть “истина” (true), то выполняется оператор, расположенный за ключевым словом then (на экран выводится значение переменной F); если же его значение “ложь” (false), то выполняется оператор, расположенный за ключевым словом else (вычисляется квадрат значения переменной F и результат помещается в ячейку с именем R).

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

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

ЗНАТЬ

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

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

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

Выражениями формального языка являются термы и формулы.

Основное назначение терма - обозначать некоторый объект.

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

Сложные термы строятся по определенным правилам путем применения к простым термам допустимых в языке функций.

Формулы образуются из термов, к которым применены допустимые в языке операторы.

Синтаксис языка - совокупность правил построения осмысленных выражений - включает в себя:

1. правила построения термов и формул;

2. правила интерпретации термов и формул;

3. правила вывода одних формул и термов из других формул и термов.

Важное практическое значение имеют такие формальные языки, как язык логики и языки программирования.

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

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

УМЕТЬ

ЗАДАНИЕ 1

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

Если в этом языке программирования зарезервированные слова? Если да, то приведите примеры зарезервированных и не зарезервированных слов.

Что в языках программирования можно рассматривать как термы и формулы?

ОТВЕТ. В алфавит языка программирования входят все символы, которые можно использовать при написании программ.

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

Формулами языка программирования являются допустимые в нем операторы: ввода, вывода, присваивания, условный, цикла и т.п.

ЗАДАНИЕ 2

Если вы изучали основы формальной логики, то:

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

2. проинтерпретируйте формулу: x ((x)  (x)) или  (А  А) = 1

ОТВЕТ. 2) - это закон непротиворечия, суть которого: никакое высказывание не может быть истинным и ложным одновременно.

ЗАДАНИЕ 3

Что является алфавитом десятичной системы счисления?

Каково основное правило образования (записи) чисел в этой позиционной системе счисления?

ОТВЕТ. Алфавит: десятичные цифры, десятичная точка (или запятая) и знаки плюс и минус. Правило: вес цифры в числе зависит от ее позиции в записи числа.

ЗАДАНИЕ 4

Каким образом может быть проинтерпретировано слово двоичного алфавита “0100 1001 0100 0110” в известной вам системе программирования (пробелы вставлены для удобства восприятия)?

ОТВЕТ. В языке Pascal эти два байта могут быть интерпретированы как строка символов “IF”, как два числа типа byte - 73 и 70, как одно число типа integer - 20758 (18758 ???).

ЗАДАНИЕ 5

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

РАСШИРЬ СВОЙ КРУГОЗОР

В формальных языках как ни в каких других велика роль знака, понимаемого в широком смысле этого слова. Некоторые аспекты использования знаков рассматривались нами ранее, но есть смысл поговорить об этом более подробно.

Причина возникновения знаков достаточно очевидна: большинство объектов познания и деятельности не доступны непосредственному восприятию в процессе познания и предъявлению в процессе коммуникации.

Знак (гр.  - знак, лат.транскрипция - semeion) - это материальный объект, выступающий в качестве представителя некоторого другого объекта, свойства или отношения и используемый для приобретения, хранения, переработки и передачи сообщений (информации, знаний).

ПРИМЕЧАНИЕ 1. Вместо слова “знак” в схожем смысле употребляются другие понятия:  “имя”, “термин”, “обозначение”.

По определению одного из создателей теории знаков (семиотики) Ч.П.Пирса, знак - это такой элемент x, который заменяет субъекту некоторый элемент y (денотат) по некоторому признаку.

Соответственно, денотат - это то, что данный знак обозначает в конкретной ситуации.

Денотат некоторой языковой абстрактной единицы (от лат. denoto - обозначаю) - множество объектов, которые могут именоваться данным знаком.

ПРИМЕЧАНИЕ 2. Вместо слова “денотат” в логике употребляют другие (тождественные, синонимические) названия: чаще всего “значение”,  “обозначаемое”.

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

ПРИМЕЧАНИЕ 3. Термин “концепт” имеет синонимы: “смысл”, “смысл знака”.

НАПРИМЕР, в слове “животное” мы обнаруживаем древнее значение слова “живот” - жизнь. Животные отличаются не наличием живота, а тем, что они живые, им присущ живот-жизнь. Таким образом, концепт знака “животное” - понятие живого существа, детонат - любое конкретное живое существо, которое имеется в виду в данной знаковой ситуации.

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

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

Иконическое отношение между означающим и означаемым - это, по Ч.Пирсу, “простая общность по некоторому свойству”. Знаки-копии (iconic signs) - воспроизведения, репродукции, которые сходны с обозначаемым (например, фотографии, отпечатки пальцев).

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

Для построения формальных языков важен именно этот тип знаков (см. параграф первой главы об основном тезисе формализации).

ПРИМЕЧАНИЕ 4. Символические знаки иногда называют символами. По мысли выдающегося русского философа П.А.Флоренского символ есть “бытие, которое больше самого себя. Символ - это нечто, являющее собою то, что не есть он сам, большее его, и однако существенно чрез него объявляющееся”. Например, мифическое существо грифон, сочетающее в себе льва и орла, является одним из символов Иисуса Христа.

Часто бывает, что знак, впервые возникший как иконический, впоследствии становится знаком-символом.

НАПРИМЕР, буква  в финикийской азбуке называлась “алеф” - бык (она напоминает голову быка). Тогда она была иконическим знаком. В греческом же языке эта буква не связана с быком и становится знаком-символом.

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

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

Денотатами далеко не всегда являются реально существующие предметы и совокупности таких предметов. Множество примеров денотатов, не являющихся объектами реальности, содержится в известной сказке Л. Кэрола “Алиса в стране чудес”. В ней же образно сформулирован принцип возникновения таких денотатов:

“Жить-то он жил (Мартовский заяц- прим авт.), а быть-то он не был”. В этой связи и русская присказка “жил да был” вовсе не кажется тавтологией.

Структура знака описывается так называемым “треугольником Фреге” (по имени выдающегося немецкого логика, много сделавшего для развития теории формальных языков). В другой терминологии он называется “семантическим треугольником” или треугольником Огдена и Ричардса. Он устанавливает связь между знаком, денотатом знака и концептом знака.

Рис. 4.3.1. Треугольник Фреге

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

1) Синонимия - ситуация, заключающаяся в полном или частичном совпадении значений различных знаков:

Рис. 4.3.2. Схема синонимии

2) знаки могут иметь один и тот же денотат, но обладать разным смыслом (денотативное тождество). Например, знаки “sin 30°” и “1/2” имеют один и тот же денотат, то есть именуют одно и то же действительное число, но смысл этих знаков различен:

Рис. 4.3.3. Схема денотативного тождества

3) Полисемия (многозначность)- наличие у знака более одного значения:

Рис. 4.3.4. Схема полисемии

ИНТЕРЕСНЫЙ ФАКТ

Историческая справка

Первые шаги к созданию формального языка логики были сделаны еще в период античности. Аристотель (384-322 д н.э.) ввел в употребление буквенные переменные для субъектов и предикатов простых категорических высказываний, а глава школы стоиков Хрисипп (ок. 281-208 до н.э.) и его ученики - переменные для высказываний в целом. В XVI веке Р.Декарт (1596-1659) создал основу современного формального языка математики - буквенную алгебру, а Г.В.Лейбниц (1646-1716) перенес Декартову символику в логику. Основным языком логики в то время был естественный язык. Осознавая существенные синтаксические и семантические недостатки естественного языка (громоздкость, многозначность и неточность выражений, нечеткость синтаксических правил и т.п.), Лейбниц сформулировал тезис о том, что без создания специального искусственного языка - “универсального исчисления” - дальнейшее развитие логики невозможно. Но лишь в конце XIX века идея Лейбница получила развитие в исследованиях Дж.Буля (1815-1864), С.Джевонса (1835-1882), Э.Шредера (1841-1902) и других - появилась алгебра логики.

Дальнейшее развитие языка логики связано с именами Дж.Пеано (1858-1932) и Г.Фреге (1848-1925). Пеано ввел ряд принятых в современной математике символов, в частности “”, “”, “”, для обозначения соответственно отношений принадлежности, объединения и пересечения множеств. Фреге построил аксиоматическое исчисление высказываний и предикатов, в котором содержались все основные элементы современных логических исчислений.

Опираясь на результаты, полученные Фреге, и используя модифицированную символику Пеано, Б.Рассел (1872-1970) и А.Н.Уайтхед (1861-1947) в совместном труде “Принципы математики” (1913) сформулировали основные положения формального языка логики.

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

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

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

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

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

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