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

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

С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс, - пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.

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

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

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

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

Природу неоднозначности можно объяснить на примере все того же дерева разбора для фразы “Мать любит дочь” (см. рис. 1).

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

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