Сол жақты рекурсивті және шынжырлы ережелердің шығарылуы

Оң жақ рекурсивті ережесі бар әрбір – грамматикасы үшін сол жақ рекурсивті ережесі жоқ эквивалентті Г грамматикасын құруға болады.

Эквивалентті грамматика құру тәсілі келесідей:

Айтылған тәсілмен сол жақты рекурсиялы –де барлық ережелерді ауыстыра келе грамматикасын аламыз және де себебі грамматикаларда шығарылған әрбір шынжыр грамматикаларда құрылуы мүмкін. және –гі шығару реттерін қарастырайық. грамматикаларда шынжырды шығару түрі келесідей:

– грамматикаларда осы шынжыр былайша шығарылады:

Өзгеру техникасын көрсету үшін мысал қарастырайық. грамматикасын өзгерту қажет, ол

кестесімен берілген.

Мазмұндалған тәсілге сүйене келе ережесін және ережесіне, ал және ережесіне өзгертеміз. Нәтижесінде келесі кестедегі грамматикасын аламыз:

және оның құрамында сол жақ рекурсивті ереже жоқ.

болатын түріндегі грамматика ережесі шынжырлы деп аталады.

Шынжырлы ережесі құрамында бар , –грамматикасы үшін оған эквивалентті шынжырлы ережесі жоқ грамматикасын құруға болады. Дәлелдеу ойы келесіде: егер грамматика схемасы түрінде болса, онда ондай грамматика түріндегі схемамен эквивалентті болады, себебі шынжырындағы схемалы грамматикадағы шығару схемалы грамматикасында ережесінің көмегімен алынады.

Жалпы жағдайда ақырғы пайымдауды төменгіде келтірілгендей дәлелдеуге болады: –ды екі және , жиындарына бөлеміз және құрамына барлық түріндегі ережелер енеді. барлық ережесі үшін ереже жиындарын табамыз. Ал оларбылай құрылуы керек: егер және –де ережесі бар (бұнда сөздігінің шынжыры) болса, онда –ға ережесін енгіземіз. , және барлық жат жиындарын біріктіру тәсілімен жаңа схемасын құрамыз.

Сонда берілген грамматикаға эквивалентті және түріндегі ережесі құрамында жоқ грамматикасын аламыз.

Мысал ретінде грамматикасынан төмендегі кестелі шынжыр ережелерін шығаруды орындаймыз:

Алдымен грамматика ережесін екі ішінаралық жиынға бөлеміз:

Әрбір -дің ережесі үшін сәйкес ішінаралық жиын құрамыз:

Нәтижесінде грамматиканың шынжыр ережесінсіз ізделіп отырған келесі түрдегі кестесін аламыз: