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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Қысқартылмайтын грамматикалардың түрленуі

түріндегі ереже жоюшы ереже деп аталады.

Ал грамматика қысқартылмайтын немесе жою ережелерінсіз грамматика деп келесі жағдайларда аталады:

1. егер грамматика кестесінде жою ережелері болмаса

2. немесе грамматика кестесінде грамматикасының бастауыш символы және оң жағында кездесетін түріндегі бір ғана ереже болса.

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

Әрбір жою ережесінің құрамында бар грамматикасы үшін оған эквивалентті түріндегі қысқартылмайтын грамматикасын құруға болады.

Қысқартылмайтын грамматиканы құру жою ережелерінде терминал еместерді шығару нәтижесінде алынған қосымша ережелерді құру жолымен берілген грамматика ережелер санының көбеюін көздейді. Қосымша ережелер құру үшін грамматиканың барлық ережелерінде жою терминал емес символдарды барлық мүмкін бос шынжырлармен алмастыру қажет. Егер грамматикада түріндегі ереже мен грамматиканың басқа ережелерінің оң жағының құрамына енетін символы болса, онда бастапқы жаңа символын енгізіп, ережесін төмендегі екі жаңа ережемен алмастыру: және .