Елиминација једноструких правила

Нека је дата КС-граматика $G\,=\,(\Sigma ,\,N,\,P,\,S)$. Претпоставимо да је у граматици G нема некорисних симбола, ни ε-правила. Поступак елиминације једноструких правила се своди на поступак тражења свих извођења облика:

$X\,\Rightarrow ^{*}\,Y,\,\,\,\,X,\,Y\in N.$

Овај поступак се врши рекурзивно полазећи од једноструких правила. Кад год се пронађе извођење горњег облика, правилима која на левој страни имају X додају се десне стране свих правила која нису једнострука, а која на левој страни имају симбол Y, док се једнострука Y-правила уклањају. Овако трансформисана граматика може имати некорисних симбола, које треба елиминисати. Добијена граматика је еквивалентна полазној граматици, а нема некорисних симбола, као ни једноструких или ε-правила.

Пример

У граматици ослобођеној од ε-правила:

(1) $T\rightarrow S\,|\,\epsilon$

(2) $S\rightarrow S(S)\,|\,(S)\,|\,S()\,|\,()$

једино једноструко извођење је $T\Rightarrow S$. Заменом симбола S на десној страни правила (1) досном страном правила (2), добија се следећа граматика без једноструких правила:

(1) $T\rightarrow \epsilon \,|\,S(S)\,|\,(S)\,|\,S()\,|\,()$

(2) $S\rightarrow S(S)\,|\,(S)\,|\,S()\,|\,()$

Погледајте још

• Лева рекурзија
• Елиминација некорисних симбола
• Елиминација е-правила