Нормальная форма Хомского: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Нормальная форма Хомского'''(''Chomsky normal form'') - ''Контекстно-свободная грамма...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Нормальная форма Хомского'''(''Chomsky normal form'') | '''Нормальная форма Хомского'''(''[[Chomsky normal form]]'') — | ||
''Контекстно-свободная грамматика'' <math>G | ''[[Контекстно-свободная грамматика]]'' <math>\,G | ||
= (N, \Sigma, | = (N, \Sigma, P, S)</math> находится в ''нормальной форме Хомского'' (или в ''[[бинарная нормальная форма|бинарной нормальной форме]]''), если | ||
каждое правило из <math>P</math> имеет один из следующих видов: | каждое правило из <math>\,P</math> имеет один из следующих видов: | ||
(1) <math>A\longrightarrow BC</math>, где <math>A | (1) <math>A\longrightarrow BC</math>, где <math>\,A,B</math> и <math>\,C</math> принадлежат <math>\,N</math>; | ||
(2) <math>A\longrightarrow a</math>, где <math>a\in\Sigma</math>; | (2) <math>A\longrightarrow a</math>, где <math>a\in\Sigma</math>; | ||
(3) <math>S\longrightarrow e</math>, если <math>e\in L(G)</math>, причем <math>S</math> не | (3) <math>S\longrightarrow e</math>, если <math>e\in L(G)</math>, причем <math>\,S</math> не | ||
встречается в правых частях правил. | встречается в правых частях правил. | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
Текущая версия от 12:12, 16 мая 2011
Нормальная форма Хомского(Chomsky normal form) — Контекстно-свободная грамматика [math]\displaystyle{ \,G = (N, \Sigma, P, S) }[/math] находится в нормальной форме Хомского (или в бинарной нормальной форме), если каждое правило из [math]\displaystyle{ \,P }[/math] имеет один из следующих видов:
(1) [math]\displaystyle{ A\longrightarrow BC }[/math], где [math]\displaystyle{ \,A,B }[/math] и [math]\displaystyle{ \,C }[/math] принадлежат [math]\displaystyle{ \,N }[/math];
(2) [math]\displaystyle{ A\longrightarrow a }[/math], где [math]\displaystyle{ a\in\Sigma }[/math];
(3) [math]\displaystyle{ S\longrightarrow e }[/math], если [math]\displaystyle{ e\in L(G) }[/math], причем [math]\displaystyle{ \,S }[/math] не встречается в правых частях правил.
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.