Спирина, М.С. Дискретная математика

В отличие от естественного язык формальной системы пред­ ставляет собой совокупность цепочек в некотором алфавите. К формальным в частности относятся искусственные языки, пред­ назначенные для общения человека с машиной, — языки про­ граммирования. Правила формальной грамматики рассматривают правила вывода (продукции) как элементарные операции, кото­ рые применяются в определенной последовательности к исход­ ной цепочке (аксиоме) и порождают лишь правильные цепочки. Последовательность правил, используемых в процессе порожде­ ния некоторой цепочки, является ее выводом. Определенный та­ ким образом язык представляет собой формальную систему. . С какой целью изучаются формальные системы? Каковы возможности объектов, изучаемых в данной теории, т.е. какие множества могут порождаться формальными системами? Для ответов на эти вопросы необходимо показать конкретные средства, аксиомы и правила выводов, которые могут привести к конкретным моделям. Итак, формальные системы задаются сле­ дующим образом. 1. Выделяем алфавит А —совокупность символов, которые сле­ дует понимать единственным определенным образом. Каждый эле­ мент (символ) алфавита принято называть буквой, а совокупность символов — словом или выражением над А. Следовательно, слово длины т — кортеж, т. е. произвольный элемент из Ат. Например, пусть А — русский алфавит, дополненный запятой, точкой, араб­ скими цифрами и пробелом: А = {а, б, ю, я, 0, 1, ..., 9, «, », «.», «_»}. Тогда ах = Овода_%, 1 е Aw, а2 = ыва.ц е А5. Очевидно, что множеством всех выражений над алфавитом А будет бесконечное множество A U A2 U A3 U ... U Ат U ... = Q Ат, которое назовем С. т=\ 2. Из множества всех слов С выделяем некое подмножество F a С. Это подмножество весьма произвольно, т.е. вводится «руками», а в качестве характеристического свойства, отличающего F от C \F , можно условно указать, что его составляют только те выражения, которые имеют смысл. Например, слова ладья и лютый мороз над алфавитом А из п. 1 имеют смысл в русском языке (задание F), а слова ълотс и 2й\к,щ_ — не имеют: ълотс g F. Элементы множе­ ства F называются формулами над алфавитом А. Произвол задания F очевиден. Например, для понимающего русский язык человека ладья имеет смысл, а для человека, не знакомого с русским язы ­ ком, нет особой разницы между наборами символов ладья и ълотс, т. е. формулы над одним и тем же алфавитом он задаст по-другому. 3. Рассмотрим множество F". Пусть f - ( f , f 2 , . . . , / , ) е Fn — набор формул. Образуем декартово произведение F 'x F и выделим из него некое подмножество R\ R с Fn х F. Из гл. 1 известно, что такая конструкция называется отношением между двумя множе- 210