Теория формальных языков и грамматик — это направление математической лингвистики, которое изучает методы описания формальных грамматик языков, построение способов и алгоритмов анализа принадлежности цепочек языку, а также алгоритмов трансляции алгоритмических языков на машинный язык.
Введение
Лингвистика – это наука о языке. Математической лингвистикой является наука, которая занимается формальными методиками создания и исследования языков. Теорией формальных грамматик является подраздел математической лингвистики, который занимается изучением методов описания формальных грамматик языков, построение способов и алгоритмов анализа принадлежности цепочек языку, а также алгоритмов трансляции алгоритмических языков на машинный язык.
Толчком к созданию и усовершенствованию данной теории стало развитие средств вычислительной техники и, следовательно, необходимость в средствах коммуникации пользователей с электронными вычислительными машинами (ЭВМ). В любом варианте использования ЭВМ обязана понимать какой-нибудь язык, на котором пользователь сможет предоставить ей алгоритм решения задачи и начальные данные. Любая ЭВМ обладает собственным языком машинных команд, которые обычно представлены в двоичном коде и отражают отдельные операции процессора. Процессы автоматизации программирования привели к реализации сначала языков ассемблера, а далее и алгоритмических языков высокого уровня, трансляция с которых в машинные коды стала выполнять сама ЭВМ. Программы, которые осуществляют такую трансляцию, то есть, перевод с одного языка на другой, именуются программами трансляции или просто трансляторами.
С проблемой трансляции на машинный язык сталкивается большинство проектировщиков программного обеспечения. Людям свойственно формировать новые языки. Все автоматизированные системы обязаны понимать определённый входной язык запросов. Новые информационные технологии подразумевают привлечение конечных пользователей, то есть, специалистов в конкретной сфере, но не в сфере вычислительной техники и технологии программирования, к разрешению своих конкретных задач при помощи ЭВМ. Для высококачественного разрешения данной проблемы между пользователем и ЭВМ обязан функционировать специальный интеллектуальный интерфейс, то есть, пользователь может выполнять постановку задачи и получать итоги их разрешения в терминологии понятной ему предметной сферы.
Таким образом, требуется формирование обширного набора предметно-ориентированных языков. Специалисту в сфере программного обеспечения необходимо знать, как формируются языки и их программная поддержка.
Основы теории формальных языков и грамматик
Для объяснения языка машине, следует иметь четкое представление об его устройстве и о том, как человек его понимает. Для создания транслятора, требуется обладать алгоритмом перевода текста в те операции, которые необходимо исполнить, а это, в свою очередь, предполагает формализацию языка. Задачи формализации языка и призвана решить математическая лингвистика. Естественные языки обладают слишком большой сложностью, и формализовать их целиком пока никому не удалось. Алгоритмические языки, наоборот, уже проектируются с расчётом на возможность их формализации. Теория формальных языков является самой развитой ветвью математической лингвистики, которая является, по существу, методом объяснения языка машине.
Язык - это набор предложений (фраз), которые построены по некоторым правилам. Грамматика – это свод правил, которые определяют принадлежность фразы языку.
Каждый язык обязан удовлетворять свойствам разрешимости и однозначности. Язык считается разрешимым, если за определённое время возможно определить, что фраза или предложение принадлежат данному языку. Язык является однозначным, если каждая из фраз может быть понята одним единственным образом.
Главными разделами грамматики являются синтаксис и семантика. Синтаксисом называется набор правил, которые определяют правильность формирования предложений языка. Семантикой является набор правил, которые определяют семантическую или смысловую правильность предложений языка. Предложение может быть синтаксически верно построено, но с позиций семантики может считаться неверным.
Формальным языком является математическая абстракция, которая возникла как обобщение стандартных лингвистических понятий естественного языка. Теория формальных языков занимается изучением, как правило, синтаксиса языков и является основой синтаксически управляемых процессов преобразования, к которым можно отнести трансляцию, ассемблирование и компиляцию.
Алфавитом является, не бесконечное множество символов, которое используется в языке. Языком является множество предложений, а предложением считается цепь символов определённого алфавита. Любая конечная очерёдность символов алфавита является цепочкой. К примеру, a, b, c, ab, aaca могут считаться цепочками в алфавите £ = {a, b, c}.
Таким образом, можно сказать, что определённый язык L является некоторым множеством цепочек в некотором алфавите Е. Существуют определённые методики описания этого языка. Если L включает в свой состав конечное количество цепочек, то самым простым способом может стать составление списка всех цепочек этого языка. Тем не мене, для большинства языков не представляется возможным или является нежелательной установка верхней границы длины для самой длинной цепочки. То есть, нужно рассматривать язык, который содержит сколь угодно большое число цепочек. Следовательно, их невозможно описать простым перечислением цепочек. Требуется выполнить условие, чтобы описание языка было не бесконечным (имело конечный объем), а сам язык может являться, по сути, бесконечным. Существует ряд методов таких описаний. Одним из главных методов является использование порождающей системы, именуемой грамматикой.
Грамматикой языка является множество объектов:
G = (VT, VN, R, S)
Здесь:
- VT обозначает множество терминальных символов (терминалом является конечный, неделимый символ).
- VN обозначает множество нетерминальных символов (понятий).
- R является множеством правил грамматики.
- S является начальным, выделенным символом грамматики (аксиомой грамматики).
