Содержание курса
Дүкендік автоматтың тұрғызылуы
жүктеу/скачать 2,16 Mb.
|
111 tokkojina m.a. khurast. tilder men avtomattar teoriyasi
| 3.4 Дүкендік автоматтың тұрғызылуы
шарттарына жауап беретін грамматика үшін келесі анықтама тән. Анықтама. Әрбір грамматикасы үшін грамматикасы тудыратын тілді қолданысқа жіберетін детерминалданған дүкендік автоматын құруға болады. Берілген грамматикасы үшін дүкендік автоматты құру міндеті келесі тәсілмен беріледі. грамматикасы берілген және автоматын анықтайтын объектілерді анықтау қажет. Автомат берілген грамматика тудыратын тілдер шынжырын жіберуі қажеттігін ескере отырып, қабылдаймыз. Автоматты мазмұндауды жеңілдету үшін бастапқыда, аяқтаушыда, яғни және болып келетін , жай-күйінде болатын айтарлық. Дүкендік алфавит ретінде қабылдайық. Функциялардың орын ауыстыруды берілген грамматика ережелерінің ТАҢДАУ жиынын қолданып келесі тәсілмен орындаймыз: Әрбір түрінде терминалды символмен бастайтын грамматика ережесі үшін автоматының командасын құрамыз, бұнда -шынжырының айналық көрінісі болып табылады. Әрбір түріндегі терминалды емес символмен басталатын грамматика ережесіне үшін автоматының командасын құрамыз, бұнда -кіріс бүршігінің қозғалмауынсыз пайда болған автомат командасы, ал шынжырының айналық көрінісі. Әрбір түріндегі грамматика жоюшы ережесі үшін автоматының командасын құраймыз. Әрбір грамматика ережелерінің оң жағының немесе ортасында орналасқан терминалды символы үшін командасын құрамыз. Аяқтаушы күйге көшу үшін командасын құрамыз. Автоматтық бастапқы конфигурациясы ретінде келесі берілген кіріс шынжырымен формуласын қолданамыз. Келтірілген ережелерді пайдаланып , грамматикасы үшін төмендегі дүкендік автомат құрамыз: Алдымен әрбір ережеге ТАҢДАУ жиынын құрып, ол грамматика грамматикасы бола алатындығын тексереміз: (1) ТАҢДАУ =АЛҒАШҚЫ = (2) ТАҢДАУ =АЛҒАШҚЫ (3) ТАҢДАУ =АЛҒАШҚЫ (4) ТАҢДАУ АЛҒАШҚЫ (5) ТАҢДАУ КЕЛЕСІ =КЕЛЕСІ Сол жағында символымен және сол жағында символымен ережелері үшін ТАҢДАУ шынжырында бірдей элементтер жоқ, соған сәйкес қарастырылып жатқан грамматика грамматика класына жатады. ТАҢДАУ функциясын пайдаланып ізделіп отырған автоматтарға сәйкес командалар құрамыз: (1) (2) (3) (4) (5) Жабылатын жақшалар (2) ережесінің аяғында орналасқанын ескеріп командасын құрамыз. Сондай-ақ аятаушы соңғы күйге көшеді: командасын құрамыз. автомат жұмысын . Кірісшынжыр мысалында тексереміз және конфигурация тізбегін аламыз: ол кіріс шынжырын құрылған автомат жіберетінін көрсетеді. жүктеу/скачать 2,16 Mb. Достарыңызбен бөлісу:
|