Виды формальных грамматик

Методы и системы искусственного интеллекта

Лекция 3

Формальные грамматики и семантические сети. Фреймы

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

Словарь (алфавит) (V) – конечное непустое множество символов (элементов). Элементы – буквы, слова, образы, математические знаки и др.

Морфема – элементарная единица слова.

Цепочка w (предложение) – конечная последовательность символов. Цепочки образуются с помощью конкатенаций (объединений). |w| - длина цепочки.

Язык над данным алфавитом – произвольное (возможно, бесконечное) множество предложений в этом алфавите.

Формальная грамматика – это четверка G = (V_T, V_N, P, S), где:

V_T – алфавит терминальных (основных) символов, из этих символов строятся языковые цепочки;

V_N – алфавит нетерминальных (вспомогательных) символов, конечное непустое множество, вспомогательные символы обозначают классы слов или словосочетаний, причем

V_N ∩ V_T = Æ; V_N È V_T = V – алфавит грамматики G;

P – множество правил подстановки (или продукций);

S – начальный/корневой символ (цель грамматики, аксиома), выделенный нетерминальный символ, который означает класс языковых объектов, для которых предназначена данная грамматика, SÎ V_N.

Длина вывода – число применений правил вывода.

Законченный вывод цепочки – не существуют никакой другой, выводимой из неё.

Основные определения теории формальных грамматик (продолжение)

V* – все возможные цепочки символов (предложения) алфавита V.

V+ – множество V*\{Λ, где Λ – пустая цепочка).

Правило подстановки (элемент множества P) будет иметь вид:

α → β, где α Î V+, β Î V*,

причем хотя бы один символ предложения α должен быть нетерминальным.

В любом предложении вхождение цепочки символов α может быть заменено цепочкой β:

(" γ, δ Î V*) γ α δ Þ γ β δ

В этом случае говорят, что β выводима из α.

Символ «→» применяется при записи правил вывода.

Символ «Þ» используется для обозначения возможности вывода одного предложения из другого в результате применения некоторого количества (одного или нескольких) правил грамматики.

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

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

Γ (G) – язык, порождаемый грамматикой G и содержащий все терминальные предложения (и только их), выводимые из начального символа S:

Γ (G) = {α | (α Î V_T*) & (S Þ α)}

Виды формальных грамматик

Распознающие – для любой распознаваемой цепочки она решает, является ли эта цепочка правильной с точки зрения конкретного языка.

Порождающие – может построить любую правильную цепочку.

Преобразующие – для любой правильной цепочки строит её отображение в виде правильной цепочки.

Пример 1. Дано:

алфавиты V_T = {a, b}, V_N = {S, A, В};

правила подстановки P = {S → AS, S → SB, S → Λ, A → ab, B → ba}.

В грамматике с такими компонентами могут быть выведены любые цепочки вида (ab)ⁿ (ba)^m.

Например: S Þ AS Þ AAS Þ AASB Þ AAB Þ abAB Þ ababB Þ ababba.

Выводы:

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

• Конечный набор правил может порождать язык, содержащий бесконечное количество предложений.

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

V_T = {a, b}, V_N = {S}, P = {S → abS, S → Sba, S → Λ },

порождает тот же язык, что и грамматика, рассмотренная выше.