Приклад.

Маємо граматику:

R = { I ®aIb,

I ®c,
A ®bI,
A ®a },

знаходимо, що A є недосяжним символом.

КВ-граматика називається приведеною, якщо вона не містить марних (непродуктивних і недосяжних) символів.

 

6.4. Виключення ліворекурсивних правил

 

Ряд граматик потребують виключення ліворекурсивних та ланцюгових правил.

Правило видуA ® a A , деA Î V_A , a Î(V_т ÈV_A)^* , називається праворекурсивним, а правило виду A ® Aa -ліворекурсивним.

Для кожної КВ-граматики Г, що містить ліворекурсивні правила, можна побудувати еквівалентну граматику Г', що не містять ліворекурсивних правил.

Щоб показати техніку перетворення, розглянемо приклад.