«Соңғы автоматтар және формальдік тілдер теориясы»


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



жүктеу 14,81 Mb.
бет5/127
Дата21.05.2018
өлшемі14,81 Mb.
#15467
1   2   3   4   5   6   7   8   9   ...   127

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

Енгізу проблемасы – берілген грамматикаға сай алгоритм құру және ол сол тілге сай келетінін мүмкіндік береді;

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

Бағалау проблемасы – алгоритм мәнінің дұрыстығын тексеру шарты.

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

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

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



Грамматикада анықталған 3,2 разрядында -ға шығу ережесінде екеуінің біреуі  тізбегінде терминальды емес болуы керек. Праграммалау тілінің сипаттамасы және оларды оқып білу көбінесе грамматика тілінде қызықты болады және шығару ережесі дәлелдеуді талап етеді

Формальды грамматиканың анықталу облысында [3, 6, 9, 34, 35,48] Хамаскидің классификациясы қабылдайды, грамматиканы ереже түріне байланысты 4 класқа бөледі:грамматиканың түрі және грамматиканың жалпы түрі G=(N, P, S) бұл грамматика У шығу ережесінің түрінде , ол V*NV*,V* .

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



Бірінші грамматика түрі немесе конспект- тәуелді грамматика бұл G=(N, P, S) граммтикасы шығу ережесі түрінің 1А 212 одан 1, 2V,AN,V+. Конспект оң және сол жақ 1және 2 аталуы бойынша сәйкестендіріледі және тізбектеледі. Олар шығу ережесінің тапсырмасы бойынша шарт орындалады: конспект 1,2 тізбектері әр уақытта терминальды емес грамматикада  және  тізбегімен ауыстырылады.

Конспект тәуелді грамматика тілде конспект тәуелді тіл деп те аталады. Грамматикада конспект тәуелді грамматика мен тіл кластарын сәйкестендіреді, оны [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



Теорема 2.2: Егер грамматикада G=(Vn, Vt, P,S)- конспект байланысы немесе рекурсивті болса

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


Хомский формальдық тілдер иерархиясы

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



Теорема 4.5.- Хомскидің нормальді түрі. Мүмкін граматика кез келген КС-тілді туындайды, онда барлық ережелер түрі немесе терминалды емес ,а- терминалды .)

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   127




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау