Дүкендік автоматтың тұрғызылуы

шарттарына жауап беретін грамматика үшін келесі анықтама тән.

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

Берілген грамматикасы үшін дүкендік автоматты құру міндеті келесі тәсілмен беріледі. грамматикасы берілген және автоматын анықтайтын объектілерді анықтау қажет.

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

Дүкендік алфавит ретінде қабылдайық.
Функциялардың орын ауыстыруды берілген грамматика ережелерінің ТАҢДАУ жиынын қолданып келесі тәсілмен орындаймыз:

- Әрбір түрінде терминалды символмен бастайтын грамматика ережесі үшін автоматының командасын құрамыз, бұнда -шынжырының айналық көрінісі болып табылады.

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

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

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

- Аяқтаушы күйге көшу үшін командасын құрамыз.

Автоматтық бастапқы конфигурациясы ретінде келесі берілген кіріс шынжырымен формуласын қолданамыз.

Келтірілген ережелерді пайдаланып , грамматикасы үшін төмендегі дүкендік автомат құрамыз:

Алдымен әрбір ережеге ТАҢДАУ жиынын құрып, ол грамматика грамматикасы бола алатындығын тексереміз:

(1) ТАҢДАУ =АЛҒАШҚЫ =

(2) ТАҢДАУ =АЛҒАШҚЫ

(3) ТАҢДАУ =АЛҒАШҚЫ

(4) ТАҢДАУ АЛҒАШҚЫ

(5) ТАҢДАУ КЕЛЕСІ =КЕЛЕСІ

Сол жағында символымен және сол жағында символымен ережелері үшін ТАҢДАУ шынжырында бірдей элементтер жоқ, соған сәйкес қарастырылып жатқан грамматика грамматика класына жатады. ТАҢДАУ функциясын пайдаланып ізделіп отырған автоматтарға сәйкес командалар құрамыз:

(1)

(2)

(3)

(4)

(5)

Жабылатын жақшалар (2) ережесінің аяғында орналасқанын ескеріп командасын құрамыз.

Сондай-ақ аятаушы соңғы күйге көшеді: командасын құрамыз. автомат жұмысын . Кірісшынжыр мысалында тексереміз және конфигурация тізбегін аламыз:

ол кіріс шынжырын құрылған автомат жіберетінін көрсетеді.

Рлеме танушылар

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

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

Анықтама.Шынжыр негізі деп қарастырылып жатқан оң жақтап шығару кезінде қолданылған ақырғы ереженің оң жағының кіруін айтады. Келтірілген шынжырды тануды орындайтын дүкендік автомат жұмысын келесі түрде көрсетуге болады:

Кесте 3.1 - -грамматикалары

Дүкен	Кіре беріс	Іс-әрекет
		ауысу
		ауысу
		ұю (1)
		ауысу
		ауысу
		ұю (1)
		ауысу
		ұю (4)
		ұю (3)
		ұю (2)
		жіберу

Детерминалданған өрлеу танушылар кез келген -грамматикалары үшін емес, тек қана бұндай грамматикалардың нақты кластары үшін ғана құрылады. -грамматикасының ішіндегі ішінаралық ең тараған -грамматикалар.

Бұл грамматикалар солдан оңға қарағанда шынжырды тануды қамтамасыз етеді. Ол туралы (Left) әрібі айтып тұр. (Right) әрібі оралу орындайтынын айтады. k параметрі шынжырдың оралуы үшін k артық емес символ көруге болатынын көрсетеді. Жалпы жағдайда -грамматикасы өте күрделі болғандықтан тәжірибеде -грамматикалық ішіндегі кластары: , немесе -жай (Simple) кіріс танушыларын жайға тұрғызу мүмкіншілігін беретін грамматикалар қолданылады.

Date: 2016-07-25; view: 385; Нарушение авторских прав