Премахване на верижни правила от граматика

Определение:
Верижно правило(единично правило) е правило от формата [math]A\rightarrow B[/math] , където [math]A[/math] и [math]B[/math] са нетерминали.

Съдържание

Постановка на проблема[редактиране]

Нека [math]\Gamma[/math] е граматика без контекст, съдържаща верижни правила. Изисква се да се конструира еквивалентна граматика [math]\Gamma'[/math] , която не съдържа верижни правила. Проблемът с премахването на верижни правила от граматика възниква, когато се опитвате да я редуцирате до нормална форма на Чомски.

Алгоритъм[редактиране]

Определение:
Верижна двойка(единична двойка) е подредена двойка [math](A,B)[/math], в която [math]A\Rightarrow ^* B[/math] , използвайки само верижни правила.

Алгоритъм за премахване на верижни правила от граматиката:

  1. Намерете всички верижни двойки в граматиката [math]\Gamma[/math] .
  2. За всяка верижна двойка [math](A,B)[/math] добавете към граматиката [math]\Gamma'[/math] всички правила от формата [math]A\rightarrow\alpha[/math] , където [math]B\rightarrow\alpha[/math] е неверижно правило от [math]\Gamma[/math] .
  3. Премахнете всички верижни правила

Можете да намерите всички верижни двойки по индукция:

Основа.[math](A,A)[/math] е верижна двойка за всеки нетерминал, тъй като [math]A\Rightarrow ^* A[/math] прави нула стъпки.

Индукция.Ако двойка [math](A,B)[/math] е верижна двойка и има правило [math]B\rightarrow C[/math] , тогава [math](A,C)[/math] е верижна двойка.

Лесно е да се разбере, че такъв алгоритъм ще намери всички верижни правила на граматиката [math]\Gamma[/math] и само тях.

Коректност на алгоритъма[редактиране]

Доказателство:[math]\triangleright[/math]

[math]\Rightarrow [/math] Нека покажем, че [math]L(\Gamma) \subseteq L(\Gamma')[/math] . Нека [math]w\in L(\Gamma)[/math] . Тогава [math]w[/math] има ляво поколение [math]S\overset> w[/math] . Където и да се използва верижното правило в лявото извеждане, нетерминалът от дясната страна става най-левият в изходната верига и незабавно се заменя. По този начин лявото генериране в [math]\Gamma[/math] може да бъде разбито на поредица от стъпки, в които нула или повече верижни правила са последвани от неверижно правило. Имайте предвид, че всяко неверижно правило, предшествано от безверижни правила, формира такава стъпка. Но чрез конструкцията на [math]\Gamma'[/math] всяка от тези стъпки може да бъде изпълнена по едно от неговите правила. Така [math]S\overset> w[/math] , т.е. [math]w\in L(\Gamma')[/math] .

[math]\Leftarrow [/math] Нека покажем, че [math]L(\Gamma') \subseteq L(\Gamma)[/math] .

Нека [math]w\in L(\Gamma')[/math] , т.е. [math]S\overset> w[/math] . Тъй като всяко [math]\Gamma'[/math] правило е еквивалентно на последователност от нула или повече [math]\Gamma[/math] верижни правила, последвани от неверижно правило от [math]\Gamma[/math] , [math]\alpha> \beta[/math] последвано от [math]\alpha\overset> \beta[/math] . Така всяка стъпка на генериране в [math]\Gamma'[/math] може да бъде заменена с една или повече стъпки в [math]\Gamma[/math] . Събирайки тези последователности от стъпки, получаваме, че [math]S\overset> w[/math] , т.е. [math]w\in L(\Gamma)[/math] .

[math]\triangleleft[/math]

Време за изпълнение на алгоритъма[редактиране]

Този алгоритъм работи в [math]O(\left \Gamma \right ^ 2)[/math] .

Пример[редактиране]

Помислете за граматиката: [math] \begin A\rightarrow Ba\\ B\rightarrowCb\\ C\rightarrow DDc \end[/math] , което има две верижни правила [math]A\rightarrow B[/math] и [math]B\rightarrow C[/math] .

  1. Нека създадем верижна двойка за всеки нетерминал. Сега наборът от верижни двойки ще се състои от [math](A, A)[/math] , [math](B, B)[/math] , [math](C, C)[/math] и [math](D, D)[/math] .
  2. Разгледайте верижното правило [math]A\rightarrow B[/math] . Тъй като има верижна двойка [math](A, A)[/math] , чийто втори елемент съвпада с левия нетерминал от правилото, добавете към множеството двойката [math](A, B)[/math] , чийто първи елемент е същият като намерения, а вторият е равен на десния нетерминал от текущото правило.
  3. Нека повторим втората точка за правилото [math]B\rightarrow C[/math] и двойката [math](B, B)[/math] . Сега наборът от верижни двойки ще се състои от [math](A, A)[/math] , [math](B, B)[/math] , [math](C, C)[/math] , [math](D, D)[/math] , [math](A, B)[/math] и [math](B, C)[/math] .
  4. Повторете втората точка за правилото [math]B\rightarrow C[/math] и двойката [math](A, B)[/math] и получаваме набора [math]\lbrace (A, A), (B, B), (C, C), (D, D), (A, B), (B, C), (A, C)\rbrace[/math] .
  5. За всяка двойка добавете нови правила към [math]\Gamma'[/math]:
  6. [math]A\дясна стрелка b[/math] за [math](A, B)[/math]
  7. [math]A\rightarrow c[/math] и [math]A\rightarrow DD[/math] за [math](A, C)[/math]
  8. [math]B\rightarrow c[/math] и [math]B\rightarrow DD[/math] за [math](B, C)[/math]
  9. Останалите двойки вериги няма да добавят нови правила.