XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 113
Текст из файла (страница 113)
Доказать, что алгебраическая система уравнений всегда имеет наименьшее решение и что язык в алфавите У является контекстно-свободным тогда и только тогда, когда он являетсл компонентой наименьшего решения некоторой алгебраической системы уравнений. У к а з а н и е: установите взаимно однозначное соответствие между алгебраическими системами уравнений и КС-грамматиками, отождествив нетерминалы грамматики с неизвестными системы уравнений. Далее, используя формулу наименьшей неподвижнои точки, покажите, что компонента Х; и-го прибли(8) жения решения алгебраической системы есть язь1к, состоящий из всех таких цепочек в алфавите У, что они выводятся из нетерминала Х,, и высота дерева вывода каждой из них не превьппает в. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТ.у РЫ Учебннкн и учебные пособил Архангельский А.А.
Канторовская теория множеств. Мз Изд-во Моск. ун-та, 1988. 112 с. Азо А., Ульман Дж. Теория синтаксического анаяиза, перевода и компиляции: Пер. с англ: В 2 т. Т. 1. Мз Мир, 1978. 612 с. Ахо А., Хонкрофтп Дж., Улыбок Дж. Построение и аналвэ вычислительных алгоритмов: Пер. с англ. Мз Мир, 1979. 536 с. Барто Т., Бирнэо97 Г. Современная прикладкал алгебра: Пер.
с англ. Мз Мир, 1976. 400 с. Белоусее А.И., Мортпыное Б.В., Щешинин А.Н. Лекции по дискретной математике. Мз Изд-во МГТУ им. Н.Э.Баумана, 1994. 96 с. Бозомолое А.М., Салий В.Н. Аю.ебраические основы теории дискретных систем. Мз Наука, 1997. 368 с. Гладкий А.В. Формальные грамматики и языки. Мз Наука, 1973. 386 с. Гретпвер Г. Общак теория решеток: Пер. с англ. Мз Мир, 1982.
456 с. Весшигнеее В.А. Применения теории графов в программировании. Мз Наука, 1985. 352 с. Коргополое М.К., Мерз сякое Ю.К. Основы теории групп. Мз Наука, 1972. 240 с. Колмогорое А.Б., Драэалнн А.Г. Введение в математическую логику. Мз Иэд-во Моск. ун-та, 1982. 120 с. Кон П. Унвверсальная алгебра: Пер. с англ. Мз Мир, 1968. 352 с. Крнсшафидес Н.
Теория графов. Алгоритмвческвй подход: Пер.'с аезл. Мз Мвр, 1978. 432 с. Кун Д., Бейэ Г. Компьютернея математика: Пер. с англ. Мз Наука, 1990. 384 с. Курошоесний К., Мосшоесний А. Введение в теорию множеств: Пер. с англ. Мз Мнр, 1970. 416 с. Лекции по теории графов / В.А, Вме ьичее, О.Б.
Мельников, В.Б. Сореаное, Р.И. Тышкевич Мз Наука, 1990. 384 с, 721 Народов В,Н., Осипова В.А. Курс дискретной математики. Мс Изд-во МАИ, 1992. 264 с. Нивмашуллин Р. Сложность булевых функпзш. Мс Наука, 1991. 240 с. Плоткин Б.И., Гринаваз ЛЯ., Гварамия А.А. Элементы алгебраической теории автоматов.
Мс Высш. пш., 1994 191 с. Савомаа А. Жемчужвны теории формальных языков: Пер. с англ. Мс Мир, 1986. Сикорски Р. Булавы алгебры: Пер. с англ. Мс Мир, 1969. 375 с. ШвнфилдДж. Математическая логика: Пер. с англ. Мс Наука, 1975. 528 с. Шияаноеич Ю. А. Введение в современную математику: (Начальшве понятия). Мс Наука, 1965. 376 с.
Яблонскиб С.В. Введение в дискретную математику. 3-е нзд. Мс Высш. шк., 2001. 384 с. Задачники Гаврилов Г.П., Саножснко А.А. Сборник задач по дискретной математике. 2-е взд. Мс Наука, 1992. 368 с. Лавров И.А., Максшвова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.
3-е изд. Мс Физматлит, 1995. 255 с. Сборник задач по авгебре / Под ред. А.И. Косшрикина. Мс Наука, 1987. 352 с. Дополнительная литература Акришас А. Основы компьютерной алгебры с приложениями: Пер. с англ. Мс Мвр, 1994. 544 с. Бував Дж., Джерри Р. Вычвслимость и логика: Пер. с англ. Мс Мир, 1994. 396 с. Вирш Н.
Алгоритмы и структуры данных: Пер. с англ. Мс Мир, 1989. 360 с. Глушков В.М., Цвбтплин Г.Е., Ющенко Е.Л. Методы символьной мультиобработки. Киев: Наук. думка, 1980. 252 с. Донояоу П. О взаимодополшпощих определениях // Семантика языков программирования: Сб. статей. Мс Мир, 1980. С. 222-394. Ершов Ю.Л., Палешан Е.А. Математическая логика. Мс Наука, 1979. 320 с. Кашнор Г.
Ъруды по теории множеств. Мс Наука, 1985. 430 с. 722 СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ Касьянов В.П. Оптимизирующие преобразования программ. Мс Наука, 1988. 336 с. Капыенд Б. Вычислимость. Введение в теоршо рекурсивных функций; Пер.
с англ. Мс Мир, 1983. 256 с. Кнута Д. Искусство программирования для ЭВМ: В 3 т. Т. 1: Основные алгоритмы. Мс Наука, 1976. 736 с. Коетман А. Введение в прикладную комбинаторику. Мс Наука, 1975. 480 с. Кушнер Б.А. Лекции по конструктивному математическому анализу. Мс Наука, 1973. 448 с. Мендельсон Э. Введение в математическую логику. Мс Наука, 1975. 320 с. Машросов В.Л., Сптвненко В.А. Лекции по дискретной математике. Мс МГПУ, 1997. 220 с.
Успенское В.А. Теорема Геделя о неполноте. Мс Наука, 1982. 111 с. Фоменко А.'Г. Наглядная геометрия и топология. Мс Изд-во Моск. ун-та, 1992. 432 с. НапбЬооЬ о1 ТЬеогег!са1 Сошрвсег Яс!епсе. Чо!. 1: А18оНФЬшв атк1 Сошр1еюту. Чо1. 2: Рогша! Мот!е!в апг! Яешапс!св. Е!вот!ег (ХогтЬ Но!!авгЦ, 1990. Ктнсй $У., Яа!оптов А. Яешптпбв, Аз!вше!а, Ьапбпабев. Ярг!пбег, Вег1пц 1986. Периодическая литперптпура Белоусов А.И.
Алгоритм обобтцевной сортировки и его применение в диалоговых обучакнцих программах // Вестник МГТУ. Сер. Приборостроение. 1993. !03. С. 118-126. Белоусов А.И., Пастузовскнб А.В. Ориентированные гиперграфы и системы подстановок // Фундаментальная и прикладная математика. 1996. 1!ь4. С.
1163-1186. Гоавн Дзс.А., Мсэвгвр Ж. Модели и равенство в логическом программировании // Математическая логика в программированви: Сб. статей. Мс Мир, 1991. С. 274-310. Ершов А.П. О сущности трансляцни // Программирование. 1977.
Ьь 5. С. 21-38. Кораблнн Ю.П., Иалншов СД. Событийная семантика схем программ языка взаимодействия последовательных процессов // Программирование. 1993. ЬьЗ. С. 48-61. 723 Нгиял С.А. Функпионаяьные языки программирования // Программировыпсе. 1991. №5. С. 77-86. Скотлтл Д. Набросок математической теории вычислений // Киберне. тическвй сборник. №14.
Мс Мир, 1977. С. 107-121. С!гепзш Д. Теория решеток, типы данных и семантика // Данные в языках программирования: Сб. статей. Мс Мир, 1982. С. 25-53. Тарасюк К.В. Понятия эквивалентностей дяя разработки параэяеяьвых систем с использованием сетей Петри // Программирование. 1998. №4. С. 19-39. Хоар Ч. Непротиворечивые вэаимодопоэншощие теории семантики языков программирования // Семантика языков программирования: Сб. статей.
Мз Мир, 1980. С. 196-221. Ре Во57гет,7.Ит., эиссет 7.7. Ргосеээеэ апб бепогаС!опа! зешапС!сз о1 сопсиггепсу. 1п1огшаС1оп апб Сопгго1, 1982. № 54. Р. 70-120. Ве Воет Р.Я., Во!Сел,7.,7., Кой 7.В., Ро1атЫеаас С. Яешапг!с Мобесэ Гог сопсштепС 1об!с 1аибиабеэ // ТЬеогейса1 СошрШег Яс1епсе.
1991. № 86. Р. 3-33. уелгел К. Ап 1псгобисйоп со сЬе ТЬеогейса1 Азрессэ о1 Со!оигеб Респ' 17егз // Ьесгиге 17огеэ ш Сошриг. Яс!. 1994. № 803. Р. 230-272. Кисей Ит. АигошаСа апб 1апбиэбиз бепегайэед Со ю-сопС!пиоиэ эешнбпбэ // ТЬеогес!са! Согприс. Зсй 1991. №79. Р. 137-150. Китса Р. А Сошрапэоп о1 Р!пИе апд Сейи1аг Аисошаса // Ьесг. Ыосеэ !и Сошриг.
Яс!. 1994. 57 841. Р. 484-493. Ресеа К. Ецшта1епсе, гег!ис!оп апд шш!шыайоп о1 йшсе аисошага отех эешкбпбэ // ТЬеогес!са1 Сошрисег Яссеисе. 1991. г7 88, Р. 269 — 285. Ясйшесй В. А18еЬгыс СЬыассепзагюп о1 Недис1Ые Р!оисЬэхсз // Л. Сошрис. Яузсеш Яс!. 1983. Ч. 27. Р. 165-199. Тбетаа Ит, Ьоб!са! Зрес1йсайопз о1 1пйшге Сошригагюпз // |ее!иге 1!огсз ш СошриС. Зсг.
1994. Х 803. Р. 583-621. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Аванцепочка 675 Автомат 494 — конечный 498, 502 -- детерминированный 506 -- кввзидетерминированный 506 — — минимальный 533 — — полностью определенный 506 — — с выходом 552 — магазинный 625 Автоматы конечные эквивалентные — минимальные изоморфные 537 Автоморфизм 244 — графа 346 — множества 42 Аксиома 473 — теории 699 Аксиомы кольца 135 — полукольца 175 — полл 140 Алгебра 117 — булеза 208 — — двухэлементная 210 -- одноэлементнав 211 — кватернионов 141, 168 — конечная 117 конечно порожденнав 232 Кэпи 170 многосортная 266 порожденнзя множеством 232 универсальная 117 цепей неориентированного графа 359 Алгебры многосортные изоморфные 270 -- однотипные 268 — однотипные 120 Алгоритм Демукрона 351 — Квайна — Мак-Клоски 410 — Крзскала 307 — сортировки 302 — Флойда — Уоршелла — Клине 339 — эффективный 307 Алфавит 462 — входной 495 -- конечного автомата 503 — — конечный мешины Тьюринга 570 — — МП-автомата 626 — выходной 552 — магазинный МП-автомата 627 — нетерминавьный 473 — объединенный 473 — терминальный 473 Анализатор 673 Анализ беступиковый 674 — восходящий 674 — нисходящий 674 — однопроходный 674 — „разверткой" 674 — „сверткой" 674 — „сверху вниз" 674 — „снизу вверх" 674 Антисимметричность 63 Антицепь 77 Аргумент операции 113 725 Базис Жегаэкина 398 — стандартный 396 Биекцил 1, 42 Бикомпонента 286 Бином Ньютона 1, 100 Блок управления автомата 495 Буква 462 — входная конечного автомата 503 Булеан множества 34 Вектор арифметический Ч, 39 — булез 210 -- единичный 210 — — нулевой 210 — значений булевой функции 387 — модуля 267 Верх магазина 627 Вершина 276 — дерева внутренняя 598 — достижимая 278 — конечного автомата заключительная 502 --- начальная 502 — стека 318 Вершины смежные 277 Вес дуги 307 — ребра 307 Включение 33 Вложение 244 Вход сети 349 Вхождение главное 467 — первое 467 — слова в слово 466 Вхождения не пересекаюшиеся 467 — пересекающиеся 467 Вывод в грамматике 476 Выводимость цепочки из цепочки 475 Вывод на множестве конфигураций МП-автомата 634 — цепной 606 — цепочки левый 595 — — правый 595 Выводы цепочки эквивалентные 595 Выражение регулярное 491 Выражения регулярные эквивалентные 493 Высказывания логически эквивалентные 25 — равносильные 25 Высота вершины ориентированного дерева 300 — ориентированного дерева 300 Выход сети 349 — триггера инверсный 558 -- прямой 558 Вычитание 130 Глубина вершины ориентированного дерева 300 Голова списка 292 Головка автомата 495 Гомоморфизм 242 — графов 342 — групп 157 — группы в фактор-группу канонмческии 164 — канонический 247 — колец 166 — многосортный 270 — проектирующий 256 — строгий 244 Грамматика контекстно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
