Предмет: Тілдер мен автоматтар теориясы
Тип: Бақылау жұмыс
Объем: 10 стр.
Год: 2012
|
Закрыть
|
Мәнмәтінді-бос грамматикалар мен дүкендік автоматтар
Жоспар
1 Мәнмәтінді-бос грамматикалар мен дүкендік автоматтар 3
1.1 Тудырмайтын, жетпейтін және пайдасыз символдарды анықтау 3
1.2 Сол жақты рекурсивті және шынжырлы ережелердің шығарылуы 5
1.3 Қысқартылмайтын грамматикалардың түрленуі 7
1.4 Дүкендік автоматтар 7
1.5 Дүкендік автомат жұмысы 8
Әдебиеттер 10
1 Мәнмәтінді-бос грамматикалар мен дүкендік автоматтар
1.1 Тудырмайтын, жетпейтін және пайдасыз символдарды анықтау
Грамматиканың төрт түрінің ішінде мәнмәтінді–бос грамматика бағдарламамлау тілдеріне қосымша мен компиляциялар көз қарасынан ең негізгі болып келеді. МБ–грамматика көмегімен бағдарламамлау тілі құрылымының үлкен бөлігін анықтауға болады.
Бағдарлама тілінің конструкциясын беретін грамматикаларды құру кезінде олардың өзгеруіне сүйенуге жиі тура келеді, сондықтан алдымен МБ–грамматиканың жай, бірақ та негізгі бірнеше өзгерулерін қарастырайық. Өзгерудің бірінші түрі грамматикадан пайдасыз символдарды жоюмен байланысты. Символдар грамматикада пайдасыз болып қалуы келесі жағдайларда болады:
а) егер символ шығару кезінде алына алмаса
б) егер символдан соңғы терминалды шынжыр алына алмаса.
1.2 Сол жақты рекурсивті және шынжырлы ережелердің шығарылуы
Оң жақ рекурсивті ережесі бар әрбір МБ Г– грамматикасы үшін сол жақ рекурсивті ережесі жоқ эквивалентті Г грамматикасын құруға болады.
Эквивалентті грамматика құру тәсілі келесідей:
1.4 Дүкендік автоматтар
МБ-грамматика шынжыр құрылымын анықтайды және нақты тілдегі шынжырды құруға мүмкіндік береді.
Формалды тілдер және грамматикалармен байланысты жұмыстарда кіріс лентасынан, басқару құралы және көмекші лента ол дүкен немесе етек деп аталатын көмекші лентадан тұратын дүкендік автомат моделі қолданылады.
Кіріс лентасы торларға бөлініп, ол торларға кіріс алфавитінің символдарын жазуға болады. Кіріс лентасының бастауы (басы) бір жаққа қарай ғана – оңға немесе орнында, қозғалып тұрады. Ол тек оқып тұру қызметін ғана атқарады. Ал көмекші лента оқып оқып және жазып алу қызметтерін атқара алады.
Қарастырылып жатқан кезде бүршік астындағы позицияны дүкен шыңы деп атайды.
Әдебиеттер
1 Дмитриев, В.И. Прикладная теория информации. – М. : Высшая школа, 1989. – 319 с.
2 Игнатов, В.А. Теория информации и передачи сигналов. – М. : Радио и связь, 1991. – 279 с.
3 Первозванский, А.А. Курс теории автоматического управления: учеб. пособие . – М. : Наука, 1986. – 300 с.
