User:DKatarina/sandbox

Нормална форма Чомског

У теорији формалних језика, контекстно слободна граматика, G, је у Чомски нормалној форми (прву ју је описао Ноам Чомски) ако су сва њена продукциона правила у облику:

A → BC,   или

A → a,   или

S → ε,

гдје су A, B и C нетерминални симболи, слово a је терминални симбол (симбол који представља константну вриједност), S је почетни симбол, а ε означава празан стринг. Такође, ни B ни C не могу бити почетни симболи, а треће продукционо правило може се појавити само ако је ε у L(G), језику који производи контекстно слободна граматика G.

Свака граматика у Чомскијевој нормалној форми је контекстно слободна, и обрнуто, свака контекстно слободна граматика може бити трансформисана у еквивалентну која је у Чомскијевој нормалној форми и има величину не већу од квадрата величине оригиналне граматике.

Претварање граматике у Чомскијеву нормалну форму

Да би се граматика претворила у Чомскијеву нормалну форму, примјењује се низ једноставних трансформација у одређеном редослиједу; ово је описано у већини уџбеника о теорији аутомата. Презентација овдје слиједи Хопкрофта и Улмана (1979), али је прилагођена да користи називе трансформација из Лангеа и Леиßа (2009). Свака од сљедећих трансформација успоставља једну од особина потребних за Чомскијеву нормалну форму.

ПОЧЕТАК: Елиминисати почетни симбол са десне стране.

Увести нови почетни симбол S₀, и ново правило

S₀ → S,

гдjе је S претходни почетни симбол. Ово не мијења језик који граматика производи, и S₀ се неће појавити на десној страни ниједног правила.

ТЕРМИНАЛ: Елиминисати правила са непојединаченим терминалима

За уклањање сваког правила

A → X₁ ... a ... X_n

са терминалним симболом a који није једини симбол на десној страни, увести, за сваки такав терминал, нови нетерминални симбол Na и ново правило

N_a → a.

Промјенити свако правило

A → X₁ ... a ... X_n

у

A → X₁ ... N_a ... X_n

Ако се на десној страни јављају више терминалних симбола, истовремено замјени сваки од њих његовим одговарајућим нетерминалним симболом. Ово не мјења језик који граматика производи.

БИНАРИЗАЦИЈА: Избаци правила која имају на десној страни више од 2 нетерминална симбола.

Замјенити свако правило

A → X₁ X₂ ... X_n

са више од 2 нетерминала X₁, ..., X_n са правилом

A → X₁ A₁,

A₁ → X₂ A₂,

... ,

A_n-2 → X_n-1 X_n,

гдје су A_i нови нетерминални симболи. Опет, ово не мијења језик који граматика производи.

БРИСАЊЕ: Елиминисати ε-правила

ε-правило је правило облика

A → ε,

гдје A није S₀, почетни симбол граматике. Да бисмо елиминисали сва правила овог облика, прво одредимо скуп свих нетерминала који изводе ε. Хопкрофт и Улман (1979) називају такве нетерминале празан (nullable) и израчунавају их на сљедећи начин:

Ако постоји правило A → ε, онда је A празан. Ако постоји правило A → X₁ ... X_n, и сваки X_i је празан, тада је и A празан.

Добијамо посредну граматику замјеном сваког правила

A → X₁ ... X_n

свим верзијама у којима су неки празан X_i изостављени. У овој граматици, бришемо свако ε-правило, осим ако је лијева страна S₀, почетни симбол. Добијамо трансформисану граматику.

На примјер, у сљедећој граматици са почетним симболом S₀:

S₀ → AbB | C

B → AA | AC

C → b | c

A → a | ε

нетерминал A, и самим тим и B, је празан, док C и S₀ нису. Затим добијамо сљедећу посредну граматику:

S₀ → AbB | AbB | AbB | AbB   |   C

B → AA | AA | AA | AεA   |   AC | AC

C → b | c

A → a | ε

У овој граматици, сва ε-правила су "уграђена на мјесту позива". У сљедећем кораку, можемо их обрисати, чиме добијамо граматику:

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

B → AA | A   |   AC | C

C → b | c

A → a

Ова граматика производи исти језик као и оригинална примјер граматика,

{ab, aba, abaa, abab, abac, abb, abc, b, bab, bac, bb, bc, c}, али нема ε-правила.

ЈЕДИНИЧНО ПРАВИЛО: Елиминисати јединична правила Јединично правило је правило облика

A → B,

гдје су A, B нетерминални симболи. Да би се ово правило уклонило, за свако правило

B → X₁ ... X_n,

гдје је X₁ ... X_n низ нетерминала и терминала, додати правило

A → X₁ ... X_n

осим ако је ово јединично правило које је већ уклоњено или се уклања. Прескакање нетерминалног симбола B у резултујућој граматици је могуће због тога што је B члан јединичног затвора нетерминалног симбола A.

Редослијед трансформација

Када се одабира редослед примјене горе наведених трансформација, треба имати у виду да неке трансформације могу уништити резултат који је постигнут другима. На примјер, ПОЧЕТАК ће поново увести јединично правило ако се примјени након ЈЕДИНИЧНО ПРАВИЛО. Табела показује који редоследи су дозвољени.

Осим тога, у најгорем случају, увећање величине граматике зависи од редоследа трансформација. Користећи |G| да означимо величину оригиналне граматике G, увећање величине у најгорем случају може се кретати од |G|² до 2² |G|, у зависности од алгоритма трансформације који се користи. Увећање величине граматике зависи од редоследа између БРИСАЊЕ и БИНАРИЗАЦИЈА. Може бити експоненцијално када се БРИСАЊЕ прво обави, али је линеарно у другим случајевима. ЈЕДИНИЧНО ПРАВИЛО може довести до квадратичног увећања величине граматике.  Редослиједи ПОЧЕТАК, ТЕРМИНАЛ, БИНАРИЗАЦИЈА, БРИСАЊЕ, ЈЕДИНИЧНО ПРАВИЛО и ПОЧЕТАК, БИНАРИЗАЦИЈА, БРИСАЊЕ, ЈЕДИНИЧНО ПРАВИЛО, ТЕРМИНАЛ доводе до најмањег (тј. квадратичног) увећања.

Примјер

Сљедећа граматика, са почетним симболом Expr, описује поједностављену верзију свих синтаксички исправних аритметичких израза у програмским језицима као што су C или Algol60. Број и промјенљива се овдје сматрају терминалним симболима ради једноставности, јер у фронтенду компилатора њихова интерна структура обично није битна за парсер. Терминални симбол "^" означава степеновање у Algol60.

Expr	→ Term	| Expr AddOp Term	| AddOp Term
Term	→ Factor	| Term MulOp Factor
Factor	→ Primary	| Factor ^ Primary
Primary	→ number	| variable	| ( Expr )
AddOp	→ +	| −
MulOp	→ *	| /

У кораку "ПОЧЕТАК" горе наведеног алгоритма конверзије, само је правило S₀→Expr додато у граматику. Након корака "ТЕРМИНАЛ", граматика изгледа овако:

S0	→ Expr
Expr	→ Term	| Expr AddOp Term	| AddOp Term
Term	→ Factor	| Term MulOp Factor
Factor	→ Primary	| Factor PowOp Primary
Primary	→ number	| variable	| Open Expr Close
AddOp	→ +	| −
MulOp	→ *	| /
PowOp	→ ^
Open	→ (
Close	→ )

Након корака "БИНАРИЗАЦИЈА", добија се сљедећа граматика:

S0	→ Expr
Expr	→ Term	| Expr AddOp_Term	| AddOp Term
Term	→ Factor	| Term MulOp_Factor
Factor	→ Primary	| Factor PowOp_Primary
Primary	→ number	| variable	| Open Expr_Close
AddOp	→ +	| −
MulOp	→ *	| /
PowOp	→ ^
Open	→ (
Close	→ )
AddOp_Term	→ AddOp Term
MulOp_Factor	→ MulOp Factor
PowOp_Primary	→ PowOp Primary
Expr_Close	→ Expr Close

Пошто нема ε-правила, корак "БРИСАЊЕ" не мења граматику. Након корака "ЈЕДИНИЧНО ПРАВИЛО", добија се сљедећа граматика, која је у Чомскијевој нормалној форми:

S0	→ number	| variable	| Open Expr_Close	| Factor PowOp_Primary	| Term MulOp_Factor	| Expr AddOp_Term	| AddOp Term
Expr	→ number	| variable	| Open Expr_Close	| Factor PowOp_Primary	| Term MulOp_Factor	| Expr AddOp_Term	| AddOp Term
Term	→ number	| variable	| Open Expr_Close	| Factor PowOp_Primary	| Term MulOp_Factor
Factor	→ number	| variable	| Open Expr_Close	| Factor PowOp_Primary
Primary	→ number	| variable	| Open Expr_Close
AddOp	→ +	| −
MulOp	→ *	| /
PowOp	→ ^
Open	→ (
Close	→ )
AddOp_Term	→ AddOp Term
MulOp_Factor	→ MulOp Factor
PowOp_Primary	→ PowOp Primary
Expr_Close	→ Expr Close

На, уведени у кораку "ТЕРМИНАЛ", су PowOp, Open и Close. Аи, уведени у кораку "БИНАРИЗАЦИЈА", су AddOp_Term, MulOp_Factor, PowOp_Primary и Expr_Close.

Алтернативна дефиниција

Чомскијева редукована форма

Други начин да се дефинише Чомскијева нормална форма је:

Формална граматика је у Чомскијевој редукованој форми ако су сва њена правила производње у облику:

𝐴 → 𝐵𝐶 или 𝐴 → 𝑎,

гдје 𝐴, 𝐵 и 𝐶 су нетерминални симболи, а 𝑎 је терминални симбол. Користећи ову дефиницију, 𝐵 или 𝐶 могу бити почетни симбол. Само оне контекстно-слободне граматике које не генеришу празан низ могу се трансформисати у Чомскијеву редуковану форму.

Флојдова нормална форма

У писму у коме је предложио термин Бекус-Наур форма (BNF), Доналд Е. Кнут је споменуо да је BNF "синтакса у којој све дефиниције имају такав облик може се рећи да је у 'Флојдовој нормалној форми'",

⟨𝐴⟩ ::= ⟨𝐵⟩ ∣ ⟨𝐶⟩ или

⟨𝐴⟩ ::= ⟨𝐵⟩ ⟨𝐶⟩ или

⟨𝐴⟩ ::= 𝑎,

гдје ⟨𝐴⟩, ⟨𝐵⟩ и ⟨𝐶⟩ су нетерминални симболи, а 𝑎 је терминални симбол, јер је Роберт В. Флојд пронашао да се свака BNF синтакса може превести на горе наведени облик 1961. године. Међутим, он је повукао овај термин "јер је без сумње многима служила ова проста чињеница у њиховом раду, и то је само спорадично у односу на главне разматрање Флојдове биљешке." Иако Флојдова биљешка наводи оригинални чланак Чомскија из 1959. године, писмо Кнута то не чини.

Примјена

Поред његовог теоријског значаја, конверзија у Чомскијеву нормалну форму се користи у неким алгоритмима као предпроцесирање, на примjер у CYK алгоритму, који је алгоритам за долазно-горе парсирање за контекстно-слободне граматике, као и његовој варијанти вјероватносном CKY алгоритму.

Погледај такође

• Бекус-Наур форма
• CYK алгоритам
• Граибахова нормална форма
• Курода нормална форма
• Лема о пумпању за контекстно-слободне језике - њена доказивања се односе на Чомскијеву нормалну форму

Напомене

1. Here's the translated text:
2. то јест, она која производи истог језика
3. На пример, Хопкрофт, Уллман (1979) спојили ТЕРМ и БИН у једну трансформацију.
4. Указивање задржаних и изостављених нетерминала Н и Н, респективно
5. Ако би граматика имала правило S₀ → ε, не би могло бити "врстовано", пошто нема "позивних локација". Стога не би могло бити обрисано у наредном кораку.
6. тј. дужина написана, мерена у симболима

Даље читање

Коул, Ричард. Претварање CFG-ова у ЧНФ (Чомскијева нормална форма), 17. октобар 2007. (pdf) — користи редослед ТЕРМ, БИН, СТАРТ, ДЕЛ, ЈЕДИНИЦА.

Џон Мартин (2003). Увод у језике и теорију рачунарства. МакГрав Хил. ISBN 978-0-07-232200-2. (Стране 237–240 од одељка 6.6: поједностављени облици и нормални облици.)

Мајкл Сипсер (1997). Увод у теорију рачунарства. ПВС Публишинг. ISBN 978-0-534-94728-6. (Стране 98–101 од одељка 2.1: контекстно-слободне граматике. Страница 156.)

Чарлс Д. Елисон (2021) (20. август 2021). Основе рачунарства: Приступачан увод у формални језик. Фреш Сорцес, Инк. ISBN 9780578944173. (странице 171-183 од одељка 7.1: Чомскијева нормална форма)

Сипсер, Мајкл. Увод у теорију рачунарства, 2. издање.

Александар Медуна (6. децембар 2012). Аутомати и језици: Теорија и примене. Спрингер Сајенц & Бизнес Медиа. ISBN 978-1-4471-0501-5.