Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Примеры ассоциативных исчислений




 

Приведём два примера АИ, точнее, опишем их основные положения.

Исчисление высказываний. Формула называется выводимой в исчислении высказываний, если она может быть получена из конечной совокупности исходных формул путём конечного числа шагов применения правил вывода. Строго доказано, что можно выбрать такую конечную совокупность аксиом исчисления высказываний, из которой выводимы все тождественно истинные формулы. Это важное положение решает проб-лему полноты исчисления высказываний. Процесс эквивалентных преоб-разований или вывода логических следствий может быть представлен как преобразование слов, причём роль допустимых подстановок играют логи-ческие законы и аксиомы.

Таким образом, вопрос выводимости какой-либо формулы становит-ся вопросом существования дедуктивных цепочек, ведущих от слов, пред-ставляющих посылки, к словам, представляющим следствия.

В ряде интерпретаций ассоциативного исчисления, в частности в теории вывода, используются подстановки вида L ® M, которые допускают лишь подстановку слева направо (слово L в слово M). Это соответствует лабиринту, по каждому коридору которого можно двигаться только в одном направлении.

В качестве другого примера АИ рассмотрим порождение классов формальных языков (в том числе языков программирования и соответ-ствующих им трансляторов). В теории алгоритмов рассматриваются раз-личные абстрактные системы, предназначенные для моделирования функционирования дискретных систем. Их способность адекватно описы-вать сложное поведение моделируемых систем можно охарактеризовать классами порождаемых ими языков, которые определённым образом кодируют разные возможные способы функционирования систем.

Приведём неформальное описание языка.

В основе каждого языка лежит словарь. Его элементы обычно назы-вают словами, но в теории формальных языков их называют символами. Совокупности слов характеризуются тем, что некоторые из них считаются правильными предложениями языка, а другие — неправильными, или не принадлежащими данному языку. Правильность предложения определяется грамматикой, синтаксисом языка. Синтаксис определяется как множество правил или формул, которые задают множество (формально правильных) предложений.

Любое предложение можно получить из начального символа после-довательным применением правил подстановки.

Синтаксические единицы (грамматические категории) называются нетерминальными символами, а слова в данном алфавите — терми-нальными символами.

Классы языков порождаются конечными множествами правил, назы-ваемых порождающими грамматиками. Каждая грамматика представляет собой набор (A, V, P, S0),

где А — алфавит терминальных символов;

V — алфавит нетерминальных символов;

P — конечное множество продукций (правил подстановки);

S0 — начальный символ.

Обозначим А* (V*) множество всех слов в алфавите А (V).

Продукция имеет вид a ® b, где a ÎV*, b Î(AUV)*. Продукция a ® b может быть применена к некоторому слову вида d1ad2 и преобразует его к виду d1 b d2. Последовательность слов g 0, g 1,…, gn такая, что слово gi, 1 £ i £ n, полученное из слова gi -1 с помощью некоторой продукции из P, называется выводом из данной грамматики, а слово gn выводимо в ней из слова g 0. Язык, порождаемый грамматикой, — это множество всех терминальных слов (слов из А*), выводимых из слова S0 с помощью продукций из P.

 




Поделиться с друзьями:


Дата добавления: 2014-01-14; Просмотров: 502; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.