E-Book Overview
Навчальний посібник. – Чернівці: ЧНУ, 2008. – 84 c.
У навчальному посібнику вивчаються елементи теорії формальних мов (форми Бекуса-Наура, регулярні вирази, формальні граматики, розпізнавачі, скінченні автомати, магазинні автомати) та теорії скінченних автоматів. Детальніше описано регулярні мови. Розглядаються алгоритми перетворення різних форм представлення автоматних мов з одного вигляду в інший, наприклад, регулярного виразу – в праволінійну граматику та навпаки, а також алгоритми перетворення недетермінованого скінченного автомата в детермінований, алгоритми вилучення недосяжних станів, алгоритми мінімізації та інші. Алгоритми демонструються на прикладах. Наведено варіанти завдань для лабораторних робіт по темах, розглянутих у посібнику. До значної частини алгоритмів, які треба реалізувати у лабораторних роботах, надано рекомендації по програмуванню. Для студентів напряму підготовки Прикладна математика.
E-Book Content
Міністерство освіти і науки України Чернівецький національний університет імені Юрія Федьковича
Сопронюк Т.M.
Cистемне програмування Навчальний посібник
Частина І. Елементи теорії формальних мов
Чернівці ЧНУ 2008
ББК 22.181.3я73 C-646 УДК 004.4’ 4 (075.8)
Друкується за ухвалою редакційно-видавничої ради Чернівецького національного університету імені Юрія Федьковича
Сопронюк Т.М. C-646 Системне програмування. Частина І. Елементи теорії формальних мов: Навчальний посібник у двох частинах. – Чернівці: ЧНУ, 2008. – 84 c.
У навчальному посібнику вивчаються елементи теорії формальних мов (форми Бекуса-Наура, регулярні вирази, формальні граматики, розпізнавачі, скінченні автомати, магазинні автомати) та теорії скінченних автоматів. Детальніше описано регулярні мови. Розглядаються алгоритми перетворення різних форм представлення автоматних мов з одного вигляду в інший, наприклад, регулярного виразу – в праволінійну граматику та навпаки, а також алгоритми перетворення недетермінованого скінченного автомата в детермінований, алгоритми вилучення недосяжних станів, алгоритми мінімізації та інші. Алгоритми демонструються на прикладах. Наведено варіанти завдань для лабораторних робіт по темах, розглянутих у посібнику. До значної частини алгоритмів, які треба реалізувати у лабораторних роботах, надано рекомендації по програмуванню. Для студентів напряму підготовки “Прикладна математика”.
ББК 22.181.3я73 УДК 004.4’4 (075.8)
© Видавництво "Рута" Чернівецького національного університету, 2008 2
Зміст ВСТУП.......................................................................................................................... 4 ОЗНАЧЕННЯ ФОРМАЛЬНОЇ МОВИ...................................................................... 5
АЛФАВІТ І ЛАНЦЮЖКИ ...................................................................................5 ФОРМАЛЬНІ МОВИ І РЕГУЛЯРНІ ОПЕРАЦІЇ НАД МОВАМИ ..................................6 СПОСОБИ ВИЗНАЧЕННЯ ФОРМАЛЬНИХ МОВ ................................................ 8
ФОРМА БЕКУСА-НАУРА ..................................................................................9 РОЗШИРЕНА ФОРМА БЭКУСА-НАУРА.............................................................11 СИНТАКСИЧНІ ДІАГРАМИ ..............................................................................11 ГРАМАТИКИ ХОМСЬКОГО .............................................................................12 РОЗПІЗНАВАЧІ ...............................................................................................17 СКІНЧЕННІ АВТОМАТИ ..................................................................................20 МАГАЗИННІ АВТОМАТИ ................................................................................25 РЕГУЛЯРНІ МНОЖИНИ І РЕГУЛЯРНІ ВИРАЗИ ....................................................27 ПЕ