Нашар бөлінген грамматикалар. -грамматикалар

Грамматиканың келесі детерминалданған тілдерді тудыратын класы жай бөлінген грамматикалар деп аталады. Бұл грамматиканың бөлінген грамматикадан ерекшелігі грамматика кестесінде жою ережелерін қолдануға болатындығы. Құрамында жою ережелері бар бөлінген грамматика жай бөлінген грамматикалар класына жата бермейді. Жай бөлінген және грамматикаларды анықтайтын тәсілді құру үшін біз ТАҢДАУ жиыны, АЛҒАШҚЫ және КЕЛЕСІ функциялары сияқты жаңа түсініктер енгізуіміз керек.

ТАҢДАУ жиыны әрбір ереже үшін құрылады және пайда болған кезде оқылып жатқан танушы бүршігінің астында бұл ережені қолданатын терминалды символдарды өз құрамына енгізеді.

ТАҢДАУ жиынын анықтауда АЛҒАШҚЫ және КЕЛЕСІ функциялары қолданылады. АЛҒАШҚЫ функциясының аргументі ретінде толық сөздігінің кез келген шынжыры бола алады, ал АЛҒАШҚЫ функциясының мағынасы ретінде терминалдық символдар жиыны болады. Және олар шынжырынан шығарылатын шынжырдың бірінші орындарында тұра алады.

АЛҒАШҚЫ функциясының мағынасын келесі ережелерді қолданып анықтауға болады:

1 Егер шынжыры терминалды символға басталса және түрінде болса, онда АЛҒАШҚЫ () функциясы -ға тең.

2 Егер шынжыры бос шынжыр болса, онда АЛҒ .

3 Егер шынжыры терминалды емес символына басталып, түрінде болса және грамматика кестесінде ережесі бар болып, кез келген жерінде символы тұра алса: және де егер тұжырымы болмаса, онда АЛҒ функциясы біріктірілген

АЛҒАШҚЫ =АЛҒАШҚЫ ÈАЛҒАШҚЫ È...ÈАЛҒАШҚЫ

жиынын көрсетеді.

4 Егер шынжыры терминалды емес символға басталып түрінде болса, грамматика кестесінде түріндегі ережесі енеді және жою терминал емес символы болып танылады, яғни бар болса, онда функция келесідей:

АЛҒАШҚЫ =АЛҒАШҚЫ ÈАЛҒАШҚЫ ÈАЛҒАШҚЫ È...ÈАЛҒАШҚЫ

КЕЛЕСІ функциясының аргументі ретінде терминалды емес, мысалы символы табылады, ал КЕЛЕСІ функциясының мағынасы ретінде шынжырда терминал емес символынан кейін жүре алатын терминалдар жиыны болады. КЕЛЕСІ функциясының мағынасы келесі ережелерге сәйкес орындалады:

1) Егер грамматика кестесінде келесі түрдегі

және барлық шынжыры болса, онда

КЕЛЕСІ = АЛҒАШҚЫ ÈАЛҒАШҚЫ È...È Û

Дүкендік автоматтардың ауысуын құру үшін қажет болатын ТАҢДАУ жиынын АЛҒАШҚЫ және КЕЛЕСІ функциялардың көмегімен келесідей анықтауға болады:, которое потребуется нам для построения переходов магазинных:

1 Егер грамматика ережесі түрінде болып, жою шынжыры болмаса,яғни басқаша айтқанда a бар болған жағдайда: ТАҢДАУ =АЛҒАШҚЫ

2 түріндегі грамматиканың жоюшы ережелеріне таңдау жиыны келесідей анықталады:

ТАҢДАУ =КЕЛЕСІ

3 Егер грамматика ережесі түрінде болса және жоюшы шынжыр болып табылса, онда

ТАҢДАУ = АЛҒАШҚЫ È КЕЛЕСІ

Енгізілген түсініктерді қолдана отырып жай бөлінген грамматика анықтамасын беруге болады. -грамматика төмендегі үш шарторындаған жай бөлінген деп аталады:

1 әр ереженің оң жағы бос шынжыр болып келсе немесе терминалды символдан басталса

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

3 сияқты терминал емес әрбір үшін бастапқы символдар жиыны :

АЛҒАШҚЫ ÇКЕЛЕСІ =