Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 6

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 2 3 4 5 < 6 > 7 8 9 10 11 12 .. 136 >> Следующая

*) Так же обычно понимается слово «язык» и в математике; например, «языком узкого исчисления предикатов» называют не множество правильно построенных формул этого исчисления, а совокупность правил обраяования таких формул (а иногда и правил преоб; разования).
**) Морфами называются наименьшие осмысленные рдцнвды языка (корни, суффиксы и Т- П-)-
16
ВВЕДЕНИЕ
элементарных символов — как грамматически правильные предложения*)). Однако понятие «слово» весьма расплывчато и нуждается в уточнении. В лингвистике такое уточнение производится несколькими различными способами; это приводит к нескольким различным понятиям, из которых для наших целей следует отметить два: а) сегмент — единица внешней стороны языка; для письменной формы языка сегмент можно понимать просто как последовательность букв от пробела до пробела; б) словоформа — единица языка, рассматриваемая одновременно в плане выражения и в плане содержания; она может пониматься как сегмент, снабженный совокупностью значений, одно из которых — лексическое (это приблизительно то же самое, что понимается под «значением слова» в толковых словарях), а остальные — грамматические («мужской род», «дательный падеж» и т. п.)**). Например, в предложении Топи печь, пора пироги печь два вхождения сегмента печь, отвечающие разным словоформам; каждое из предложений Судно на море догнал и Судно весело бежит содержит вхождение сегмента судно, и опять-таки этим вхождениям отвечают разные словоформы (в первом случае различаются как лексические, так и грамматические значения, во втором — только грамматические). Во всех лингвистических замечаниях и примерах, содержащихся в основном тексте и в приложении I, «слова» могут трактоваться либо как сегменты, либо как словоформы, но всякий раз нужно четко представлять себе различие между этими концепциями. Иная интерпретация понадобится нам лишь в приложении II.
*) Для естественных языков грамматическую правильность следует отличать от осмысленности. Так, предложение Ехала деревня мимо ямщика бессмысленно, но грамматически правильно. Для простых формализованных языков объемы понятий грамматической правильности и осмысленности обычно совпадают; например, всякое арифметическое выражение, правильным образом составленное из символов натуральных чисел, знаков сложения и умножения и скобок, имеет смысл, т. е. представляет некоторое натуральное число.
**) В трактовке понятий сегмента и словоформы мы следуем А, Д, Зализняку [Зализняк 1967, стр. 19—20].
ГЛАВА 1
ОСНОВНЫЕ понятия
§ 1.0. Некоторые предварительные пояснения
Поясним некоторые термины и обозначения — обще-математические и из теории графов, — употребляемые в литературе не всегда одинаковым образом.
Отношение «быть подмножеством» обозначается символом ?=. Запись А а В означает A s В& А Ф В.
Пустое множество обозначается 0.
Множество всевозможных упорядоченных пар элементов множества М обозначается М2. Множество всех подмножеств М обозначается 2м.
Мощность множества М обозначается ц(М).
Операции алгебры логики и кванторы обозначаются &, V, =, V, 3 соответственно.
Если р — отношение эквивалентности на множестве М, то множество классов, на которые р разбивает М, называется ф акт о р - м но жест во м множества М по отношению р и обозначается М/р. Мощность М/р называется индексом отношения р.
Множество М. с заданными на нем предикатами
?Р], ..., Рп обозначается (М; Р\....... Рп). Во всех
остальных случаях упорядоченная система объектов ..., обозначается альтернативно через (9li, ... или <Я,..............Я*).
Множество М с заданным на нем двуместным предикатом (бинарным отношением) R называется графом и обозначается, в соответствии с вышесказанным, (М; R). Вместо /?(а, b'j пишем aRb, Элементу множества М
18
ОСНОВНЫЕ понятия
называются узлами графа (М; R)*). Пара узло (а, Ь), для которой имеет место aRb, называется ду гой графа; а есть начало этой дуги, Ь — ее конец Вместо «пара (а, Ь) является дугой» говорим «из а в Ь-идет дуга» или «а подчиняет Ь». Последовательность узлов графа а0, а1.......ап (п ^ 0) называется путем
(идущим) из а0 в ап в этом графе, если для каждог i=l, ..., п из а{_) в dj идет дуга; а0 есть начал пути, а„ — его конец; число п есть длина пути. Если из а в b идет путь, говорим, что b зависит от а. (В частности, всякий узел зависит от себя.)
Узлы графа, не являющиеся началами никаких дуг, называются висячими, узлы, не являющиеся ни началами, ни концами никаких дуг, — изолированными.
Конечный граф называется дерево.м, если: а) в нем существует единственный узел (называемый корнем), который не является концом никакой дуги; б) всякий, его узел, отличный от корня, является концом точно одной дуги; в) в нем нет замкнутых путей (т. е. путей, концы которых совпадают с началами) ненулевой длины. Легко видеть, что в каждый узел дерева идет в точности один путь из корня.
Множество всех узлов дерева, подчиненных одному узлу а, называется кустом этого узла, а множество, всех узлов, зависящих от а, — группой зависимости узла а. Число элементов куста называется его шириной. Наибольшее значение ширины куста узла де--рева называется шириной дерева.
Предыдущая << 1 .. 2 3 4 5 < 6 > 7 8 9 10 11 12 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed