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

Привет, Вы узнаете о том , что такое формальные языки, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое формальные языки, формальные грамматики, аналитические грамматики , настоятельно рекомендую прочитать все из категории Компьютерная лингвистика.

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

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

Термины

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

История

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

Язык включает следующие составные части:

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

В качестве знаков языка могут выступать:

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

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

В любом языке можно выделить правильные (допустимые) и неправильные конструкции. Правила построения правильных текстов составляют синтаксис языка. Описание соответствия между смыслами и текстами составляют семантику языка.

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

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

• машинный перевод с одного естественного языка на другой;
• разработка трансляторов;
• распознавание образов.

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

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

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

Универсальные языки используются для общения людей в повседневной жизни.

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

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

* Зависимость синтаксиса от семантики (смысла). Например, окончания слов могут зависеть от того, к каким объектам относятся эти слова, одушевленным или неодушевленным. Для примера рассмотрим две похожих фразы:

"Я увидел пень" (Что?).

"Я увидел оленя" (Кого?).

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

* Возможность появления парадоксальных предложений. Парадоксальные предложения построены так, что их нельзя отнести ни к истинным, ни к ложным. Примером парадоксального предложения является фраза: "Данное предложение является ложным".

* Зависимость смысла от ситуации.

*Изменчивость языка во времени.

*Большое число синтаксических правил с многочисленными исключениями.

12.3. формальные языки и их особенности.

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

• Независимость синтаксических правил от смысла.
• Невозможность появления парадоксов.
• Строгость синтаксических правил и отсутствие исключений.
• Конечное число синтаксических правил.

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

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

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

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

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

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

• — набор (алфавит) терминальных символов
• N — набор (алфавит) нетерминальных символов
• P — набор правил вида: «левая часть» «правая часть», где:
  • «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
  • «правая часть» — любая последовательность терминалов и нетерминалов
• S — стартовый (или начальный) символ грамматики из набора нетерминалов.

Вывод

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

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

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

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

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

Кроме того, выделяют:

• Неукорачивающиеся грамматики. Каждое правило такой грамматики имеет вид , где . Длина правой части правила не меньше длины левой .
• Линейные грамматики. Каждое правило такой грамматики имеет вид , или , то есть в правой части правила может содержаться не более одного вхождения нетерминала .

Применение

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

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

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

Терминальный алфавит:

 = {'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}

Нетерминальный алфавит:

  { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

Правила:

1. Об этом говорит сайт https://intellect.icu  . ФОРМУЛА  ФОРМУЛА ЗНАК ФОРМУЛА                (формула есть две формулы, соединенные знаком)
2. ФОРМУЛА  ЧИСЛО                               (формула есть число)
3. ФОРМУЛА  ( ФОРМУЛА )                         (формула есть формула в скобках)
4. ЗНАК  + | - | * | /                          (знак есть плюс или минус, или умножить, или разделить)
5. ЧИСЛО  ЦИФРА                                 (число есть цифра)
6. ЧИСЛО  ЧИСЛО ЦИФРА                           (число есть число и цифра)
7. ЦИФРА  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1, или ... 9 )

Начальный нетерминал:

ФОРМУЛА

Вывод:

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

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

(ФОРМУЛА) (ФОРМУЛА ЗНАК ФОРМУЛА)

(ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА)

(ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ЧИСЛО)

(ФОРМУЛА + ЧИСЛО) (ФОРМУЛА + ЦИФРА)

(ФОРМУЛА + ЦИФРА) (ФОРМУЛА + 5)

(ФОРМУЛА + 5) (ЧИСЛО + 5)

(ЧИСЛО + 5) (ЧИСЛО ЦИФРА + 5)

(ЧИСЛО ЦИФРА + 5) (ЦИФРА ЦИФРА + 5)

(ЦИФРА ЦИФРА + 5) (1 ЦИФРА + 5)

(1 ЦИФРА + 5) (1 2 + 5)

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

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

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

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

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

Синтаксическое подразделение в рамках формальной системы.

Определение формального языка

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

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

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

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

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

Операции формального языка

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

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

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

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

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

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

До становления современной логики, в «Органоне» Аристотеля, а именно в работе «Об истолковании» были заданы основы понимания и значения логики. Введение кванторов должно было решить проблему общности множеств, не решаемую в рамках субъектно-предикатного анализа Аристотеля, хотя в логике термов появляется новый интерес, а именно попытки построить исчисление в духе силлогистики Аристотеля, но используя свойства общности кванторов из современной логики.

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

• Теоретико-модельная семантика, архетип семантики теории истинности Альфреда Тарского, основанной на его Т-схеме, является одной из ключевых концепций модельной теории. Это один из наиболее распространенных подходов. Основная его идея в том, что смысл различных частей утверждения задаются всевозможными способами рекурсивного задания группы функций интерпретации, отображающих предложения на некоторые заранее заданные математические множества. Так, интерпретация логики предикатов первого порядка задается отображением термов в универсум, и отображение предикатов в значения истинности «истина» и «ложь». На модельно-теоретической семантике основан подход в теории смысла под названием семантика условной Истины, который впервые был предложен Дональдом Девидсоном. Семантика Крипке по сути вносит некоторые дополнения к семантике Тарского.
• Теоретико-доказательная семантика связывает смысл утверждений с ролями, которые они играют в рассуждении. Герхард Генцен, Даг Правиц (швед. Dag Prawitz) и Майкл Даммет считаются основателями этого подхода. На него сильно повлияла поздняя философия Людвига Витгенштейна, особенно его афоризм «смысл — это применение».
• Семантика значений истинности(также известная как подстановочная квантификация) была предложена Рут Маркус (англ. Ruth Barcan Marcus) для модальных логик в начале 1960-х и затем развита в трудах Дана (Michael Dunn), Белнапа (англ. Nuel Belnap) и Леблана (Hugues Leblanc) в качестве стандартной логики первого порядка. Джеймс Гарсон (англ. James Garson) получил некоторые результаты в областях адекватности интенсиональных логик, снабженных такой семантикой. Условия истинности квантифицированных формул задаются исключительно в терминах истинности, без использования множеств (отсюда и название).
• Теоретико-игровая семантика недавно была возрождена Яакко Хинтиккой для логик (конечной) частично покрытой квантификации, которые изначально исследовались Леоном Хенкиным.
• Вероятностная семантика — обобщение семантики значений истинности, созданное Филдом (Hartry Field).

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

Вау!! 😲 Ты еще не читал? Это зря!

• Теория моделей

• JFLAP — программа - симулятор автоматов, машины Тьюринга , грамматик
• Синтаксический анализ
• Неоднозначная грамматика
• Задача о наименьшей грамматике

• Формальные языки и формальные грамматики
  Общие понятия	Иерархия Хомского Алфавит Слово
  Тип 0	Неограниченная грамматика Машина Тьюринга Перечислимый язык Разрешимый язык
  Тип 1	Контекстно-зависимая грамматика Контекстно-зависимый язык Линейно ограниченный автомат
  Тип 2	Контекстно-свободная грамматика Неоднозначная грамматика Контекстно-свободный язык Автомат с магазинной памятью (детерминированный) Лемма о разрастании Лемма Огдена
  Тип 3	Регулярная грамматика Регулярный язык Регулярное выражение Конечный автомат (детерминированный, недетерминированный) Минимизация ДКА Детерминизация НКА Теорема Майхилла — Нероуда
  Синтаксический анализ	LL-анализатор LR-анализатор Метод рекурсивного спуска Алгоритм Кока — Янгера — Касами

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