Формалды грамматикада үш негізгі проблемалар қарастырылады

Егер бірінші екі тапсырмалар көбіне грамматикалық сипатта болса, онда үшінші тапсырма, көбіне «алгоритмдік» сипатта болады.

Компьютердің пайда болуына байланысты, алгоритмнің нақты және құрылымына талаптар қойылады. Бұл мақсатты қанағаттандыру үшін алгоритмдік тілдер өндірілуде. Өзіне математикалық символиканы, мысалы, сандар, операциялы белгілері, айнымалы шамалар, берілулер және т.б. қосатындықтан, бұл формальды тіл, формальданған тіл болып саналады.

5. Грамматикаларды классификациялау: регулярлық, контексті

Грамматиканың жалпы түрі мәннің қызықтысын қабылдайды, олар тым бос, бұларды программалау тіліндегі синтаксисті жазуда қолдануға болады. Табиғи тілге арналған синтаксисте қолданылады. 0 грамматикалық түрдегі мысал G=( {A, S}, {0,1}, P, S) программасына негіз болады және P={S0A1, 0A 00F1,A }.

Конспект тәуелді грамматика тілде конспект тәуелді тіл деп те аталады. Грамматикада конспект тәуелді грамматика мен тіл кластарын сәйкестендіреді, оны [9] -бен дәлелдеуге де болады. Ол грамматикада қысқартылмайтын деп те аталады, шығару ережесінің  орындау кезінде мына шартты қанағаттандырады.

Демек бұл алгоритмде немесе шекті сандарды анықтау кезінде терминалды тілде не жатады немесе жатпайды. Қысқартылмаған грамматика мына мысалда көрсетілген: G=( {B,C,S} ), {a,b,c},P,S) P={S aS,B,C, S abc; CB BC, bB bb, bC bc, cC cc).

Екінші грамматикалық түрі немесе конспект бос грамматика – бұл G=(N, ,P,S) грамматика шығару ережесінің мынадай түрін береді. АВ , немесе АN,V*.

Келесі тіл Конспект тәуелді грамматиканы жеңіл оқиды және толық тексереді, сосын тілден бос тізбек шығады. Шығу ережесін жазғанда Конспект тәуелді грамматикасы лингвистикалық формуламен сәйкес келеді. Нақтырақ айтсақ, конспект тәуелді грамматикада шығу ережесінің терминалды емес грамматикасының сол жақ бөлігі лингвистикалық грамматиканың сол жақ бөлік формасымен сәйкес келеді.

Қатынас  - метолингвистикалық байланыста былай белгіленеді:  шығу ережесінің терминалды және терминалды емес тізбектерінің бөлігі – метолингвистикалық формулада екіге бөлінеді: математикалық қоңырау тізбегі және тілдің басты символдарының оң жақ бөлігі.

Үшінші грамматикалық түрі – автоматты және регулярлы грамматика бұл G=(N, ,P,S) шығару ережесінің түрі А немесе А, онда А,ВN, U{}.Автоматты грамматика тілде конспект тәуелді тілі немесе автоматты және регулярлы грамматика деп аталады.

Рекурсивті конспект-тәуелді грамматиканың байланысы

Еске түсірсек грамматика G=(Vn, Vt, P,S) - рекурсивті деген не, егер алгоритм бар болса, ол көбінесе анықталады. Кейбір нақты тізбекте хV*t нақты грамматика G-ге тең болады, егер G=(Vn, Vt, P,S)-конспекстті-тәуелді грамматикаға байланысы болса. Тексерейік, нақты грамматиканың бос сөйлемі жоқ немесе жай ғана. Ережеде S L(G1), L(G) сонда және тек сонда ғана, егер SP, L(G), және жаңа грамматика құрастыруға болады:

G=(Vn, Vt, P,S), ереже болмайды S, тағы солай P=P1/{ S}.

Грамматика G1 тағы конспект байланысы және L(G1)= L(G1)/{ }. Әрбір шешу ұзындығы сентенциалдық формада үлкейеді. V грамматикасы сөздікте К символында біріктіреді. Жалғасы, Sх1б Сентентенциялдық формасы аі, а ...,а бәрі сол бір ұзындық, P әртүрлі ұзындық тізбегі, V алфавит символы, к символ, кр ендік. Біздідің қарастырған j+1 тізбегі j>k7

Дәлелдеу: қолдану бар болса шынында  L(G1) егер осылай болса, онда грамматика ережесі S, грамматиканы аламыз, көбінесе бір тіл, немесе бос сөз. Р ережені тоқтатпайды S, қарастырылған тізбекте хV*t . Біздің тапсырмада алгоритмді табу, х L(G1) мына сұрақты шешеміз: х=n(n>0). Тm келесі бейне мүмкін. Tm=Tm-1U{a}β→αβε

Дәлелдейміз бірінші екі теореманың нормалыларды туралы КС-граматикті көрсетеміз . Әрбіреуіінде олар түрлерінде бекітеді , не барлық граматикалар эквиваленттік граматикасы ережелердің түріне шек қойылады.