WikiDer > Нормальная форма Хомского

В формальный язык теория, контекстно-свободная грамматика, грамм, как говорят, находится в Нормальная форма Хомского (впервые описано Ноам Хомский)^[1] если все это правила производства имеют вид:^{[нужна цитата]}

А → до н.э, или же

А → а, или же

S → ε,

куда А, B, и C находятся нетерминальные символы, письмо а это символ терминала (символ, представляющий постоянное значение), S - начальный символ, а ε обозначает пустой строкой. Кроме того, ни B ни C может быть начальный символ, а третье правило продукции может появиться, только если ε находится в L(грамм), язык, созданный контекстно-свободной грамматикой грамм.^{[2]:92–93,106}

Каждая грамматика в нормальной форме Хомского контекстно-свободный, и наоборот, любую контекстно-свободную грамматику можно преобразовать в эквивалент один^{[примечание 1]} который находится в нормальной форме Хомского и имеет размер не больше квадрата размера исходной грамматики.

Преобразование грамматики в нормальную форму Хомского

Чтобы преобразовать грамматику в нормальную форму Хомского, применяется последовательность простых преобразований в определенном порядке; это описано в большинстве учебников по теории автоматов.^{[2]:87–94[3][4][5]}Представленная здесь презентация следует за Hopcroft, Ullman (1979), но адаптирована для использования имен преобразований из Lange, Leiß (2009).^{[6][заметка 2]} Каждое из следующих преобразований устанавливает одно из свойств, необходимых для нормальной формы Хомского.

СТАРТ: Удалите начальный символ с правой стороны

Введите новый начальный символ S₀, и новое правило

S₀ → S,

куда S - предыдущий начальный символ. Это не меняет язык, созданный грамматикой, и S₀ не будет появляться в правой части правила.

СРОК: Отменить правила с неуединенными терминалами

Чтобы устранить каждое правило

А → Икс₁ ... а ... Икс_п

с символом терминала а будучи не единственным символом в правой части, вводим для каждого такого терминала новый нетерминальный символ N_а, и новое правило

N_а → а.

Измените каждое правило

А → Икс₁ ... а ... Икс_п

к

А → Икс₁ ... N_а ... Икс_п.

Если в правой части встречается несколько терминальных символов, одновременно замените каждый из них связанным с ним нетерминальным символом. Это не меняет язык, созданный грамматикой.^[2]:92

BIN: исключите правые части с более чем 2 нетерминалами

Заменить каждое правило

А → Икс₁ Икс₂ ... Икс_п

с более чем 2 нетерминалами Икс₁,...,Икс_п по правилам

А → Икс₁ А₁,

А₁ → Икс₂ А₂,

... ,

А_п-2 → Икс_п-1 Икс_п,

куда А_я являются новыми нетерминальными символами. Опять же, это не меняет язык, созданный грамматикой.^[2]:93

DEL: отменить ε-правила

Ε-правило - это правило вида

А → ε,

куда А не является S₀, начальный символ грамматики.

Чтобы исключить все правила этой формы, сначала определите набор всех нетерминалов, которые производят ε. Хопкрофт и Ульман (1979) называют такие нетерминалы обнуляемый, и вычислите их следующим образом:

• Если правило А → ε существует, то А допускает значение NULL.
• Если правило А → Икс₁ ... Икс_п существует, и каждый Икс_я допускает значение NULL, тогда А тоже допускает значение NULL.

Получите промежуточную грамматику, заменив каждое правило

А → Икс₁ ... Икс_п

всеми версиями с некоторыми допускающими значение NULL Икс_я Пропущено. Удаляя в этой грамматике каждое ε-правило, если его левая часть не является начальным символом, получается преобразованная грамматика.^[2]:90

Например, в следующей грамматике с начальным символом S₀,

S₀ → AbB | C

B → AA | AC

C → б | c

А → а | ε

нетерминальный А, а значит, и B, допускает значение NULL, в то время как ни один C ни S₀ Таким образом получается следующая промежуточная грамматика:^{[заметка 3]}

S₀ → АбB | АбB | АбB | АбB   |   C

B → AA | АА | АА | АεА   |   АC | АC

C → б | c

А → а | ε

В этой грамматике все ε-правила были "встроенный на месте звонка ».^{[примечание 4]}На следующем этапе их можно удалить, получив грамматику:

S₀ → AbB | Ab | bB | б   |   C

B → AA | А   |   AC | C

C → б | c

А → а

Эта грамматика создает тот же язык, что и исходный пример грамматики, а именно. {ab,аба,абаа,Abab,abac,abb,abc,б,бабушка,бак,bb,до н.э,c}, но не имеет ε-правил.

UNIT: исключить правила для юнитов

Единичное правило - это правило формы

А → B,

куда А, B являются нетерминальными символами. Чтобы удалить его, для каждого правила

B → Икс₁ ... Икс_п,

куда Икс₁ ... Икс_п это строка нетерминалов и терминалов, добавьте правило

А → Икс₁ ... Икс_п

если только это правило не было удалено (или удаляется).

Порядок преобразований

Взаимное сохранение
результатов трансформации

Трансформация Икс всегда сохраняет (Y) соотв. может разрушить (N) результат Y:
Y Икс	НАЧНИТЕ	СРОК	BIN	DEL	ЕДИНИЦА ИЗМЕРЕНИЯ
НАЧНИТЕ
СРОК
BIN
DEL
ЕДИНИЦА ИЗМЕРЕНИЯ				(Y)*
*ЕДИНИЦА ИЗМЕРЕНИЯ сохраняет результат DEL если НАЧНИТЕ звонили раньше.

При выборе порядка, в котором должны применяться вышеуказанные преобразования, необходимо учитывать, что некоторые преобразования могут разрушить результат, достигнутый другими. Например, НАЧНИТЕ повторно вводит единичное правило, если оно применяется после ЕДИНИЦА ИЗМЕРЕНИЯ. В таблице показано, какие заказы принимаются.

Более того, в худшем случае раздутие грамматического размера^{[примечание 5]} зависит от порядка преобразования. Использование |грамм| для обозначения размера исходной грамматики грамм, размер разрушения в худшем случае может составлять от |грамм|² до 2^{2 | G |}, в зависимости от используемого алгоритма преобразования.^[6]:7 Размер увеличения грамматики зависит от порядка между DEL и BIN. Это может быть экспоненциально, когда DEL выполняется первым, в противном случае - линейно. ЕДИНИЦА ИЗМЕРЕНИЯ может привести к квадратичному увеличению размера грамматики.^[6]:5 Заказы НАЧНИТЕ,СРОК,BIN,DEL,ЕДИНИЦА ИЗМЕРЕНИЯ и НАЧНИТЕ,BIN,DEL,ЕДИНИЦА ИЗМЕРЕНИЯ,СРОК приводят к наименьшему (т.е. квадратичному) разрушению.

Пример

Абстрактное синтаксическое дерево из арифметическое выражение "а^2+4*б"по примеру грамматики (верх) и его нормальная форма Хомского (Нижний)

Следующая грамматика с начальным символом Expr, описывает упрощенную версию набора всех синтаксических допустимых арифметических выражений в языках программирования, таких как C или же Алгол60. Обе номер и Переменная считаются здесь терминальными символами для простоты, так как в интерфейс компилятора их внутренняя структура обычно не рассматривается парсер. Терминальный символ "^" обозначает возведение в степень в Algol60.

Expr	→ Срок	| Expr AddOp Срок	| AddOp Срок
Срок	→ Фактор	| Срок MulOp Фактор
Фактор	→ Начальный	| Фактор ^ Начальный
Начальный	→ номер	| Переменная	| ( Expr )
AddOp	→ +	| −
MulOp	→ *	| /

На этапе «СТАРТ» над алгоритм преобразования, просто правило S₀→Expr добавляется в грамматику. После шага «TERM» грамматика будет выглядеть так:

S0	→ Expr
Expr	→ Срок	| Expr AddOp Срок	| AddOp Срок
Срок	→ Фактор	| Срок MulOp Фактор
Фактор	→ Начальный	| Фактор PowOp Начальный
Начальный	→ номер	| Переменная	| Открыть Expr Закрывать
AddOp	→ +	| −
MulOp	→ *	| /
PowOp	→ ^
Открыть	→ (
Закрывать	→ )

После шага «БИН» получается следующая грамматика:

S0	→ Expr
Expr	→ Срок	| Expr AddOp_Term	| AddOp Срок
Срок	→ Фактор	| Срок MulOp_Factor
Фактор	→ Начальный	| Фактор PowOp_Primary
Начальный	→ номер	| Переменная	| Открыть Expr_Close
AddOp	→ +	| −
MulOp	→ *	| /
PowOp	→ ^
Открыть	→ (
Закрывать	→ )
AddOp_Term	→ AddOp Срок
MulOp_Factor	→ MulOp Фактор
PowOp_Primary	→ PowOp Начальный
Expr_Close	→ Expr Закрывать

Поскольку ε-правил нет, шаг «DEL» не изменяет грамматику. После шага «UNIT» получается следующая грамматика, которая находится в нормальной форме Хомского:

S0	→ номер	| Переменная	| Открыть Expr_Close	| Фактор PowOp_Primary	| Срок MulOp_Factor	| Expr AddOp_Term	| AddOp Срок
Expr	→ номер	| Переменная	| Открыть Expr_Close	| Фактор PowOp_Primary	| Срок MulOp_Factor	| Expr AddOp_Term	| AddOp Срок
Срок	→ номер	| Переменная	| Открыть Expr_Close	| Фактор PowOp_Primary	| Срок MulOp_Factor
Фактор	→ номер	| Переменная	| Открыть Expr_Close	| Фактор PowOp_Primary
Начальный	→ номер	| Переменная	| Открыть Expr_Close
AddOp	→ +	| −
MulOp	→ *	| /
PowOp	→ ^
Открыть	→ (
Закрывать	→ )
AddOp_Term	→ AddOp Срок
MulOp_Factor	→ MulOp Фактор
PowOp_Primary	→ PowOp Начальный
Expr_Close	→ Expr Закрывать

В N_а введенные на шаге «СРОК», являются PowOp, Открыть, и Закрывать. А_я введенные на шаге "BIN", AddOp_Term, MulOp_Factor, PowOp_Primary, и Expr_Close.

Альтернативное определение

Приведенная форма Хомского

По-другому^[2]:92[7] для определения нормальной формы Хомского:

А формальная грамматика в Приведенная форма Хомского если все его производственные правила имеют вид:

${displaystyle Aightarrow, BC}$ или же

${displaystyle Aightarrow, a}$,

куда ${displaystyle A}$, ${displaystyle B}$ и ${displaystyle C}$ - нетерминальные символы, и ${displaystyle a}$ это символ терминала. При использовании этого определения ${displaystyle B}$ или же ${displaystyle C}$ может быть начальным символом. Только те контекстно-свободные грамматики, которые не генерируют пустой строкой можно преобразовать в приведенную форму Хомского.

Нормальная форма Флойда

В письме, где он предложил термин Форма Бэкуса – Наура (BNF), Дональд Э. Кнут подразумевается синтаксис BNF, «в котором все определения имеют такую ​​форму, можно сказать, что они находятся в« нормальной форме Флойда »»,

${displaystyle langle Aangle :: =, langle Bangle mid langle Cangle}$ или же

${displaystyle langle Aangle :: =, langle Bangle langle Cangle}$ или же

${displaystyle langle Aangle :: =, a}$,

куда ${displaystyle langle Aangle}$, ${displaystyle langle Bangle}$ и ${displaystyle langle Cangle}$ нетерминальные символы, и ${displaystyle a}$ это символ терминала,потому что Роберт В. Флойд обнаружено, что любой синтаксис BNF может быть преобразован в указанный выше в 1961 году.^[8] Но он отказался от этого термина, «поскольку, несомненно, многие люди независимо использовали этот простой факт в своей собственной работе, и этот момент является лишь второстепенным по отношению к основным соображениям примечания Флойда».^[9] В то время как в записке Флойда цитируется оригинальная статья Хомского 1959 года, в письме Кнута нет.

Заявление

Помимо своей теоретической значимости, преобразование CNF используется в некоторых алгоритмах в качестве этапа предварительной обработки, например, CYK алгоритм, а восходящий анализ для контекстно-свободных грамматик и его вариант вероятностный CKY.^[10]

Смотрите также

• Форма Бэкуса – Наура
• CYK алгоритм
• Нормальная форма Грейбаха
• Курода нормальная форма
• Лемма о перекачке для контекстно-свободных языков - его доказательство опирается на нормальную форму Хомского

Примечания

Рекомендации

дальнейшее чтение

• Коул, Ричард. Преобразование CFG в CNF (нормальная форма Хомского), 17 октября 2007 г. (pdf) - использует порядок TERM, BIN, START, DEL, UNIT.
• Джон Мартин (2003). Введение в языки и теорию вычислений. Макгроу Хилл. ISBN 978-0-07-232200-2. (Страницы 237–240 раздела 6.6: упрощенные и нормальные формы.)
• Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. ISBN 978-0-534-94728-6. (Страницы 98–101 раздела 2.1: контекстно-свободные грамматики. Страница 156.)
• Сипсер, Майкл. Введение в теорию вычислений, 2-е издание.
• Александр Медуна (6 декабря 2012 г.). Автоматы и языки: теория и приложения. Springer Science & Business Media. ISBN 978-1-4471-0501-5.