Нормальная форма Хомского - Chomsky normal form

В формальный язык теория, контекстно-свободная грамматика, грамм, как говорят, находится в Нормальная форма Хомского (впервые описано Ноам Хомский )^[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 алгоритм
• Нормальная форма Грейбаха
• Курода нормальная форма
• Лемма о перекачке для контекстно-свободных языков - его доказательство опирается на нормальную форму Хомского

Примечания

1. то есть тот, который производит такое же язык
2. Например, Hopcroft, Ullman (1979) объединили СРОК и BIN в единую трансформацию.
3. указывает на сохраненный и опущенный нетерминал N к N и N, соответственно
4. Если бы в грамматике было правило S₀ → ε, он не мог быть «встроенным», поскольку не имел «сайтов вызова». Поэтому его нельзя было удалить на следующем шаге.
5. т.е. письменная длина, измеряемая в символах

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

1. Хомский, Ноам (1959). «О некоторых формальных свойствах грамматик». Информация и контроль. 2 (2): 137–167. Дои:10.1016 / S0019-9958 (59) 90362-6. Здесь: раздел 6, стр. 152 и далее.
2. Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Ридинг, Массачусетс: издательство Addison-Wesley Publishing. ISBN  978-0-201-02988-8.
3. Хопкрофт, Джон Э .; Мотвани, Раджив; Ульман, Джеффри Д. (2006). Введение в теорию автоматов, языки и вычисления (3-е изд.). Эддисон-Уэсли. ISBN  978-0-321-45536-9. Раздел 7.1.5, стр.272
4. Рич, Элейн (2007). Автоматы, вычислимость и сложность: теория и приложения (1-е изд.). Прентис-Холл. ISBN  978-0132288064.^{[страница нужна ]}
5. Вегенер, Инго (1993). Теоретическая информатика - Eine algorithmmenorientierte Einführung. Leitfäden und Mongraphien der Informatik (на немецком языке). Штутгарт: Б. Г. Тойбнер. ISBN  978-3-519-02123-0. Раздел 6.2 «Die Chomsky-Normalform für kontextfreie Grammatiken», с. 149–152
6. Ланге, Мартин; Лайс, Ганс (2009). «В CNF или не в CNF? Эффективная, но презентабельная версия алгоритма CYK» (PDF). Informatica Didactica. 8.
7. Hopcroft et al. (2006)^{[страница нужна ]}
8. Флойд, Роберт В. (1961). «Замечание о математической индукции в грамматиках фразовой структуры» (PDF). Информация и контроль. 4 (4): 353–358. Дои:10.1016 / S0019-9958 (61) 80052-1. Здесь: с.354
9. Кнут, Дональд Э. (декабрь 1964 г.). «Нормальная форма Бэкуса против формы Бэкуса Наура». Коммуникации ACM. 7 (12): 735–736. Дои:10.1145/355588.365140. S2CID  47537431.
10. Джурафский, Даниэль; Мартин, Джеймс Х. (2008). Обработка речи и языка (2-е изд.). Пирсон Прентис Холл. п. 465. ISBN  978-0-13-187321-6.

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

• Коул, Ричард. Преобразование 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.