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

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

A → BC , или

A → a , или

S → ε,

где A , B и C - нетерминальные символы , буква a - конечный символ (символ, представляющий постоянное значение), S - начальный символ, а ε обозначает пустую строку . Кроме того , ни В , ни С может быть начальным символом , а третье правило производство может появиться только тогда , когда ε в L ( G ), язык производства контекстно-свободной грамматики G . ^[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

с терминальным символом a, который не является единственным символом в правой части, введите для каждого такого терминала новый нетерминальный символ N _a и новое правило

N _a → a .

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

А → Х ₁ ... а ... Х _n

к

A → X ₁ ... N _a ... X _n .

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

BIN: удалите правые части с более чем 2 нетерминалами [ править ]

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

А → Х ₁ Х ₂ ... Х _n

с более чем 2 нетерминалами X ₁ , ..., X _n по правилам

А → Х ₁ А ₁ ,

А ₁ → Х ₂ А ₂ ,

...,

A _{n -2} → X _{n -1} X _n ,

где A _i - новые нетерминальные символы. Опять же, это не меняет язык, созданный грамматикой. ^[2]^{: 93}

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

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

A → ε,

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

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

Если существует правило A → ε, то A допускает значение NULL.
Если существует правило A → X ₁ ... X _n и каждый X _i допускает значение NULL, то A также допускает значение NULL.

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

А → Х ₁ ... Х _n

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

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

S ₀ → AbB | C

B → AA | AC

C → b | c

A → a | ε

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

S ₀ → A b B | A b B | A b B | A b B | C

B → AA | A A | A A | A ε A | A C | А С

C → b | c

A → a | ε

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

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

B → AA | А | AC | C

C → b | c

А → а

Эта грамматика создает тот же язык, что и исходный пример грамматики, а именно. { ab , aba , abaa , abab , abac , abb , abc , b , bab , bac , bb , bc , c }, но не имеет ε-правил.

UNIT: исключить правила для единиц [ править ]

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

А → Б ,

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

B → X ₁ ... X _n ,

где X ₁ ... X _n - строка нетерминалов и терминалов, добавьте правило

А → Х ₁ ... Х _n

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

Порядок преобразований [ править ]

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

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

Более того, наихудшее увеличение размера грамматики ^{[примечание 5]} зависит от порядка преобразования. Использование | G | для обозначения размера исходной грамматики G размер увеличения в худшем случае может находиться в диапазоне от | G | ² к 2 ^{2 | G |} , в зависимости от используемого алгоритма преобразования. ^[6]^{: 7} Увеличение размера грамматики зависит от порядка между DEL и BIN . Он может быть экспоненциальным, когда сначала выполняется DEL , но в противном случае - линейным. UNIT может привести к квадратичному увеличению размера грамматики. ^[6]^{: 5}Последовательности START , TERM , BIN , DEL , UNIT и START , BIN , DEL , UNIT , TERM приводят к наименьшему (т.е. квадратичному) разрушению.

Пример [ править ]

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

Следующая грамматика с начальным символом Expr описывает упрощенную версию набора всех синтаксических допустимых арифметических выражений в языках программирования, таких как C или Algol60 . И число, и переменная здесь считаются терминальными символами для простоты, поскольку во внешнем интерфейсе компилятора их внутренняя структура обычно не рассматривается анализатором . Конечный символ «^» обозначает возведение в степень в Algol60.

Выражение	→ Срок	\| Expr AddOp Term	\| Срок действия AddOp
Срок	→ Фактор	\| Срок MulOp Factor
Фактор	→ Первичный	\| Фактор ^ Первичный
Начальный	→ номер	\| Переменная	\| ( Выражение )
AddOp	→ +	\| -
MulOp	→ *	\| /

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

S ₀	→ Выражение
Выражение	→ Срок	\| Expr AddOp Term	\| Срок действия AddOp
Срок	→ Фактор	\| Срок MulOp Factor
Фактор	→ Первичный	\| Фактор PowOp Первичный
Начальный	→ номер	\| Переменная	\| Открыть Expr Close
AddOp	→ +	\| -
MulOp	→ *	\| /
PowOp	→ ^
Открыть	→ (
Закрывать	→)

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

S ₀	→ Выражение
Выражение	→ Срок	\| Expr AddOp_Term	\| Срок действия AddOp
Срок	→ Фактор	\| Срок MulOp_Factor
Фактор	→ Первичный	\| Фактор PowOp_Primary
Начальный	→ номер	\| Переменная	\| Открыть Expr_Close
AddOp	→ +	\| -
MulOp	→ *	\| /
PowOp	→ ^
Открыть	→ (
Закрывать	→)
AddOp_Term	→ Срок действия AddOp
MulOp_Factor	→ Фактор MulOp
PowOp_Primary	→ Первичный PowOp
Expr_Close	→ Выражение Закрыть

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

S ₀	→ номер	\| Переменная	\| Открыть Expr_Close	\| Фактор PowOp_Primary	\| Срок MulOp_Factor	\| Expr AddOp_Term	\| Срок действия AddOp
Выражение	→ номер	\| Переменная	\| Открыть 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	→ Выражение Закрыть

Н введенный в шаге «СРОК» являются PowOp , Открыть и Закрыть . _Я введенный в шаге «БИН» являются AddOp_Term , MulOp_Factor , PowOp_Primary и Expr_Close .

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

Сокращенная форма Хомского [ править ]

Другой способ ^[2]^{: 92}^[7] определить нормальную форму Хомского:

Формальная грамматика в Хомский уменьшенный форму , если все ее правила производства имеют вид:

{\ Displaystyle A \ rightarrow \, BC}

или же

{\ Displaystyle A \ rightarrow \, а}

,

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

Нормальная форма Флойда [ править ]

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

{\ displaystyle \ langle A \ rangle :: = \, \ langle B \ rangle \ mid \ langle C \ rangle}

или же

{\ displaystyle \ langle A \ rangle :: = \, \ langle B \ rangle \ langle C \ rangle}

или же

{\ Displaystyle \ langle A \ rangle :: = \, а}

,

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

Заявление [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

^ то есть тот, который производит тот же язык
^ Например, Hopcroft, Ullman (1979) объединили TERM и BIN в одно преобразование.
^ с указанием сохраненного и пропущенного нетерминального N посредством N и N , соответственно
^ Если бы грамматика имела правило S ₀ → ε, она не могла бы быть «встроенной», так как в ней не было «сайтов вызова». Поэтому его нельзя было удалить на следующем шаге.
^ т.е. письменная длина, измеряемая в символах

Ссылки [ править ]

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

[3] то есть тот, который производит тот же язык

[8] Например, Hopcroft, Ullman (1979) объединили TERM и BIN в одно преобразование.

[9] ^ с указанием сохраненного и пропущенного нетерминального N посредством N и N , соответственно

[10] Если бы грамматика имела правило S ₀ → ε, она не могла бы быть «встроенной», так как в ней не было «сайтов вызова». Поэтому его нельзя было удалить на следующем шаге.

[11] т.е. письменная длина, измеряемая в символах

[1] Хомский, Ноам (1959). «О некоторых формальных свойствах грамматик» . Информация и контроль . 2 (2): 137–167. DOI : 10.1016 / S0019-9958 (59) 90362-6 . Здесь: раздел 6, стр. 152 и далее.

[Hopcroft.Ullman.1979-2] Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Ридинг, Массачусетс: издательство Addison-Wesley Publishing. ISBN 978-0-201-02988-8.

[4] Хопкрофт, Джон Э .; Мотвани, Раджив; Ульман, Джеффри Д. (2006). Введение в теорию автоматов, языки и вычисления (3-е изд.). Эддисон-Уэсли. ISBN 978-0-321-45536-9. Раздел 7.1.5, стр. 272

[5] Рич, Элейн (2007). Автоматы, вычислимость и сложность: теория и приложения (1-е изд.). Прентис-Холл. ISBN 978-0132288064.^{[ требуется страница ]}

[6] Вегенер, Инго (1993). Теоретическая информатика - Eine algorithmmenorientierte Einführung . Leitfäden und Mongraphien der Informatik (на немецком языке). Штутгарт: BG Teubner. ISBN 978-3-519-02123-0.Раздел 6.2 «Die Chomsky-Normalform für kontextfreie Grammatiken», с. 149–152

[Lange.Leis.2009-7] Ланге, Мартин; Лайсс, Ганс (2009). «В CNF или не в CNF? Эффективная, но презентабельная версия алгоритма CYK» (PDF) . Informatica Didactica . 8 .

[12] Хопкрофт и др. (2006)^{[ необходима страница ]}

[13] Флойд, Роберт В. (1961). «Заметка о математической индукции в грамматиках фразовой структуры» (PDF) . Информация и контроль . 4 (4): 353–358. DOI : 10.1016 / S0019-9958 (61) 80052-1 . Здесь: с.354

[knuth1964-14] Кнут, Дональд Э. (декабрь 1964 г.). «Нормальная форма Бэкуса против формы Бэкуса Наура». Коммуникации ACM . 7 (12): 735–736. DOI : 10.1145 / 355588.365140 . S2CID 47537431 .

[15] Джурафски, Даниэль; Мартин, Джеймс Х. (2008). Обработка речи и языка (2-е изд.). Пирсон Прентис Холл. п. 465. ISBN 978-0-13-187321-6.

[1]