ВУЗ:
Составители:
132
-
итерации А* и В*.
Если множество не может быть построено конечным числом правил для регу-
лярных множеств, то оно
нерегулярно.
Примеры:
1) регулярные множества: {ab, ba}* {a, a}; {b} ({c}∨ {α, ab}*);
2) нерегулярные множества: {a
n
b
n
| n>0}; {α | в цепочке α количества вхожде-
ний символов a и b совпадают}.
4. Функция
Функция
. Если Х и Y – два множества, то отображением множества Х в мно-
жество Y называют
функцию f, у которой область отправления (равная области опре-
деления) равна Х, а область прибытия равна Y. Можно также и по-другому утвер-
ждать (читать):
1) «функция f определена на Х и принимает свои значения в Y»;
2) «пусть f есть отображение Х в Y»;
3) «пусть дано отображение f: Х
→ Y» или проще: «пусть f: Х → Y».
Термины
отображение, функция, преобразование всегда будут иметь одинако-
вый смысл, а запись
f: Х
→ Y
будет указывать (читается), что «f – отображение, определенное на множестве Х со
значениями из множества Y».
Множество Х называется
областью определения или доменом функции f.
Множество Y называется
областью значения или диапазоном функции f.
Функция f, определенная на множестве Х и принимающая значения из множе-
ства Y, называется также
отображением Х в Y.
Домен и диапазон называют соответственно
первой и второй проекциями f и
обозначаются np
1
f и np
2
f.
Отображение f множества Х в множество Y называется
отображением Х на Y,
если np
2
f = Y. Отображение f множества Х в множество Y называется взаимно-
однозначным
, если образами двух любых различных элементов множества Х являют-
ся различные элементы множества Y.
Пример. Пусть Х - некоторое множество элементов информации, представленных тем
или иным образом, Y - другое множество элементов информации, а f - функция пре-
образования. Тогда преобразователь информации можно представить устройством,
реализующим отображение f: Х
→ Y одного множества на другое.
