Пример 8.2

Рассмотрим формальную грамматику, порождающую фрагмент естественного языка. Пусть Т = {а, б, ...я, А, Б, ...Я} - множество терминальных символов - букв русского алфавита. Нетерминальный алфавит строится из символов N = {Q, R, S}, где Q = {q₁,...q_n} - множество имен людей в русском алфавите, R = {r₁,...r_m} - множество глаголов, стоящих в третьем лице единственного числа настоящего времени, r_i и q_j записываются с помощью терминальных символов. Пусть система подстановок имеет вид:

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

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

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