Формальные языки это кратко

Обновлено: 07.07.2024

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

Математический язык как форма выражения научного знания использовался еще в древности при решении практических задач.

Большую роль в развитии математики как языка – метаязыка наук – сыграла математическая логика, аксиоматизировавшая ряд теории, изучившая их логику, внутреннюю структуру.

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

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

Язык, определенный с помощью алфавита (над алфавитом) X = 1, x₂, . , x_n> , – это некоторая устная, звуковая, письменная или иная форма выражения слов над X , включая синтаксис – правила образования структур из слов и словосочетаний, семантику – правила проверки правильности, смысловой однозначности и совместимости синтаксических конструкций языка , состоящих из лексем. Для устных языков (общения) нужна и фонетика – правила произношения составных частей предложения, то есть фонем.

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

Пример. В частности, семантика изучает связи вида:

"знак, структура знаков значение объект ";

синтаксис – связи вида:

$\Longleftrightarrow$

"знак, структура знаков объект ".

Пример. Запишем более кратко, сжато, точно (формализованно) факт " целое число x делится на целое число y без остатка". На математическом языке это будет иметь вид "Число x кратно числу y ". Факт, что числа x, y – целые, уже можно специально, как выше, не оговаривать, так как математическое понятие кратности это уже предполагает ( аксиома ). Запишем еще более кратко и формализованно на алгоритмическом языке Паскаль : " x mod y = 0 ". Здесь уже условие кратности область изменения аргументов не нужно оговаривать – они декларированы в языке Паскаль (в описаниях типов и операции mod ).

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

Пусть X – некоторый алфавит , X = 1, x₂, . , x_n> , а S(X) – множество слов над алфавитом X , тогда S(X) – бесконечное и счетное множество.

Формальный язык L(X) – произвольное подмножество S(X) .

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

Формальная грамматика G состоит из совокупностей: T = 1, t₂, . , t_k> – множество терминальных символов языка или множество основных понятий языка ; N = 1, n₂, . n_m> – множество нетерминальных символов языка или вспомогательных понятий, обозначений конкретных классов слов, например, глаголов или предлогов, причем во множестве N содержится n₀ – начальный символ из N ; P = 1, p₂, . p_q> – система подстановок (продукции) слов вида (x)\subset S(X)" />
в слова (x)\subset S(X)" />
или замен всех слов s₁(x) в рассматриваемой системе соотношений на слова вида s₂(x) .

$s\in S(x)$

Язык (множество слов S(X) ) задается грамматикой G(S) – структурой правил, которые позволяют порождать все слова и только их.

Грамматический анализ – процесс редукции к нетерминальному символу или слову.

Множество – словарь грамматики G . Правила вывода – это непустое множество правил вида , где , а " " – отношение вида "левое (можно) заменить на правое".

Слово выводимо из слова с помощью правила , если f_v_" />
, =v_g_v_, p_\in P" />
. Последовательность ; f_; f_; \ldots; f_t = g, t \ge 1" />
называется выводом g из f , если f_i+1 выводимо из f_i для всех . Признаком завершения процесса (последовательности) вывода является отсутствие слова, выводимого из g .

Пример. Опишем элементы естественного, например, русского языка в терминах формальных грамматик . Алфавит языка X = , T= < , и т.д.>, N = , n₀ = "предложение" . Например, пусть

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

Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.

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

Формальные языки

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

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

Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V = обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов. Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1. an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

Наконец, формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.

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

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

Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L = (здесь n — натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

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

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

Окрестностные грамматики

С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.

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

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

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

характеристики

Ограниченная среда

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

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

Грамматические правила априори

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

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

Минимальная семантическая составляющая

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

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

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

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

Символический язык

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

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

Универсальность

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

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

Точность и выразительность

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

Возможность расширения

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

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

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

Примеры

Логика

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

Математика

Объяснение этой цепочки состоит в том, что все элементы этого набора соответствуют условию быть меньше или равным 3 и в то же время больше 2. Другими словами, эта цепочка определяет число 3, которое является единственным элементом, который соответствует условиям.

Компьютерное программирование

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

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

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

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

Определения

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

Основа большинства как искусственных, так и естественных языков — алфавит.

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

Характеристики естественных языков

Как уже было сказано, все языки условно разделяют на искусственные и естественные. Между ними есть множество различий.

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

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

При этом основными функциями разговорных языков являются:

общение;
познавательная деятельность;
выражение эмоций;
воздействие на собеседника (корреспондента, если речь идет о переписке).

Характеристики искусственных языков

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

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

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

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

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

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

Сфера применения

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

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

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

Язык формальной логики

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

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

Формальная логика борется с “недостатками” естественных языков, связанных с неоднозначностью некоторых высказываний и пр. Для этой цели операции с мыслями заменяют действиями со знаками формального языка. Это исключает какую-либо неопределенность и позволяет точно установить истинность высказывания.

Особенности языков программирования

Как уже было сказано, их с некоторыми оговорками можно отнести к классу формальных.

С последними их объединяют многие синтаксические правила, а с естественными некоторые ключевые слова и конструкции.

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

Грамматики

Языки программирования, как и любые другие, имеют грамматику. Под этим термином понимают описание способа составления предложений. Грамматики описываются различными способами. В случае языков программирования они представляют собой правила, которые задаются упорядоченными парами цепочек символов двух типов: определяющих синтаксические конструкции и семантические ограничения. Задавая грамматики, сначала формально излагают правила построения синтаксических конструкций, а затем — задают семантические на одном из естественных языков.

Запись правил в графическом виде осуществляется посредством специальных диаграмм. Изначально такой подход был применен при создании языка Pascal. Однако затем он стал широко применяться и в других.

Классификация языков программирования

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

Теперь вы сможете ответить на вопрос: “Какие формальные языки вам известны?”. Ученые продолжают совершенствовать их, с целью сделать возможными решение различных практических и теоретических задач, которые на данный момент считаются неразрешимыми.

Читайте также: