Студопедия
Обратная связь


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram


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

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

Любой естественный язык возникал как средство общения людей. Именно по этой причине ему присущи такие особенности как:

· изменчивость, которая состоит в непостоянстве словарного состава языка;

· неоднозначность трактовки фраз различными людьми;

· избыточность, о чем шла речь в главе «Кодирование символьной информации».

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

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

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

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

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

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

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

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

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

Формальная грамматика задается упорядоченной четверкой {T, N, S, Р}, где Т и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р - набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид gh, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.

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





 

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

Нормальные алгоритмы Маркова

Модели структурные и функциональные

Раздел 2. АЛГОРИТМЫ. МОДЕЛИ. СИСТЕМЫ

Пример 8.1

Пример 7.9

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1549

 
 

© studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам. Ваш ip: 54.162.168.187