Гладкий - Формальные грамматики и языки - 1973, страница 3

Упомянем также об окрестностных грамматиках (некоторые косвенные сведения о них имеются в настоящей книге в 2 4.5 и упражнении 5.7), Л-грамматиках (также вскользь затронутых в $ 4.5), оценках сложности распознавания порождаемых грамматиками языков. 2) Весьма важное место отводится в книге сопоставлению грамматик с автоматами; это дает возможность представлять себе грамматики и классы грамматик не изолированно, а в некотором достаточно широком контексте и благодаря этому лучше понимать строение по- Р ождаемых грамматиками языков и работу самих грамматик. Поэтому в главах 1, 3, 4 и 5 рассматриваются Р азличные классы автоматов (собственно — машин Тьюринга) и изучаются их связи с классами грамматик.

Другой вопрос, значение которого в книге сознательно подчеркивается, — оценки сложности работы грамматик (т. е. вывода в грамматиках). Эти оценки являются важнейшим средством классификации грамматик и языков; именно они позволяют составить представление о том, как грамматика «работает». Поэтому вопрос об оценках сложности вывода в произвольных грамматиках рассматривается в начале книги— он составляет содержание второй главы; оценкам сложности вывода в грамматиках специальных типов посвящена основная часть третьей главы и вся седьмая.

3) Наряду с формальными грамматиками существуют и другие математические конструкции, специально предназначаемые для описания некоторых существенных аспектов естественного языка или для описания лингвистического исследования. Вместе с теорией грамматик теории этих конструкций составляют так называемую и атем ати ческую лингвистику. Подробнее о значении этого термина см. 1Гладкий — Мельчук 1969, стр, 15 — 22). Для цас сейчас важно лишь то, что теория грамматик — это только часть математической лингвистики, хотя н занимающая в ней центральное место. -вввдвнив Введение -Настоящая книга посвящена только теории грамматик; однако автор счел целесообразным изложить в ней в виде приложений два специальных вопроса математической лингвистики, собственно к теории грамматик не относя.щихся: способы описания синтаксической структуры .предложения и «теорию замещаемости», Это вызвано, с одной стороны, тем, что некоторыми возникающими при изучении указанных вопросов понятиями (впрочем, весьма простыми) приходится пользоваться в теории .грамматик, с другой — наличием тесной связи между лингвистическими интерпретациями теории грамматик н этих вопросов.

Кроме того, систематического и достаточно строгого изложения способов описания синтаксической структуры предложения до сих пор вообще, кажется, не появлялось в доступной широкому читателю литературе *). По стилю оба приложения несколько отличаются от основного текста книги — в них уделено сравнительно .много внимания лингвистическим приложениям, Это обусловлено самим характером материала, состоящего в значительной степени из определений понятий, вызванных к жизни не столько математическими, сколько лингвистическими соображениями.

Для чтения приложения 1 достаточно знакомства с $1.1 (или дажесего началом). Знакомство с материалом $ П1.! необходимо для чтения глав 3 — 7; остальные два параграфа приложения ! используются только в $ 6.3 (не считая одного несущественного замечания в $ 6.1), Для чтения приложения Н достаточно знакомства с Я 1.! и 1.2; материал этого приложения, именно, его второго параграфа, использован только в Я 5,2 и 8.4*«).

4) В настоящей книге слово «язык» всюду означает «множество последовательностей элементарных симво- ') Очень хорошее «нематематнческое» изложение имеется з 'статье [Пэдученэ 1964). ° «) Читателю, интересующемуся лннгннстнческнмн вопросами, можно рекомендовать прочесть обз приложения сразу после гл. 1. Прочие читатели могут ознакомиться с й П!.1 перед чтением гл. 3, с ЯП1.2, П1. 3' перед чтением гл. 6, я нз приложения П посмотреть только определение язанмозамещэемостн н лемму ПИ.!, дойдя до теоремы 6.7, н определение конфигурации, дойдя до стр. 277. лов», что в лингвистической интерпретации могло бы ть «множество текстов», в частном случае «мнох ление жество правильных текстов».

Такое словоупотреб является обычным в математической лингвистике (в по- время оно проникло и в теорию автоматов), на асхо ится с принятым в собственно лингвистике ( язы« коведении), где под языком понимают, как р п авило, не-, которую си стем у, «работающее устройство>, включаю-, б амматику *), что же касается совокупности тов на данном языке, т. е. результата его ра о тексто совокупность лингвисты называют обь р !чно «ечью».

эту совоку (такое употребление терминов «язык» и «р ! » « ечь» восхо-, дит к . де о с Ф. Соссюру). Однако использование слова сле «множество последовательностей сим« «язык» в смысл « в тео ии г амматик. волов» настолько уже укоренилось в теории гра и гих разделах математической лингвистики, что отказаться от него не представляется воз о лее, что не ви не видно чем его заменить (во всяком случае. лингв истический термин «речь» здесь не годится). 5) Формальные грамматики могут испол спользоваться. для оп с и апия различных уровней естественного языка, и синфонологического, морфологического или например фо» ча г амматики со« таксического, В любом случае задача гра б -.

м, чтобы описать, как строятся некоторые о-. стоит в том, чт лее сложные объекты из более простых: д ф ля фонологического уровня — морфы *э) из фонем, для морфологи-. ческого — слова (точнее словоформы, см. ниже) из морф, для синтаксического — предложения из слов. Пок в нашей книге лингвистическое истолкование привлекается только в иллюстративны ц, у ых елях мы будем обращаться лишь лишь к одной «естественно-языковой» интерпретации — синт — аксической, во многих отношениях бной. Таким образом, элементарные символы. самой удо ной. ак во всех лингвистических примерах будут р р ринте п ети оваться как слова (а «правильные последовательности» ') Т обычно понимается слово «язык» н н матемятнкэ; як же например, «языко м узкого исчисления нреднкзтоя» нязынз т совок нь о построенных формул этого исчисления, я уность прэннл обрязоннння таких формул (з иногда н нряэн р л и зоб! '*] яб ф языняются нэнменьшне осмысленныр едн нны н зчор<рэмн нязыня языка (корня, суффиксы н т.

и.). ВВЕДЕНИЕ элементарных символов — как грамматически правильные предложения *)). Однако понятие «слово» весьма расплывчато и нуждается в уточнении. В лингвистике такое уточнение производится несколькими различными способами; это приводит к нескольким различным понятиям, из которых для наших целей следует отметить два: а) сегм ент — единица внешней стороны языка; для письменной формы языка сегмент можно понимать просто как последовательность букв от пробела до пробела; б) ел о в о ф о р м а — единица языка, рассматриваемая одновременно в плане выражения и в плане содержания; она может пониматься как сегмент, снабженный совокупностью значений, одно из которых — л екс и ч е с к о е (это приблизительно то же самое, что понимается под «значением слова» в толковых словарях), а остальные — г р а м м а т и ч е с к и е («мужской род», «дательный падеж» н т.

п.)е'). Например, в предложении Топи печь, пора пироги печь два вхождения сегмента печь, отвечающие разным словоформам; каждое нз предложений Судно на море догнал и Судно весело бежит содержит вхождение сегмента судно, и опять-таки этим вхождениям отвечают разные словоформы (в первом случае различаются как лексические, так и грамматические значения, во втором — только грамматические). Во всех лингвистических замечаниях и примерах, содержащихся в основном тексте и в приложении 1, «слова» могут трактоваться либо как сегменты, либо как словоформы, но всякий раз нужно четко представлять себе различие между этими концепциями. Иная интерпретация понадобится нам лишь в приложении П.

ч Л * Р дует отличать от осмыслеииости. Тяк, предложение Ехала деревня милю или~ила бессмысленно, ио грамматически правильно. Для простых формелизовеиных языков объемы понятий грамматической превильиости и осмысленности обычно совпадают; например, всякое арифметическое выражение, правильным образом составленное из символов иетурельиых чисел, зников сложения и умножения и скобок, имеет смысл, т. е. представляет некоторое натуральное число.

е») П трактовке понятий сегмента и словоформы Мы следуем А, А. Звлнзияку [Зелизияк 1967, стр. 19 †2 ГЛАВА ! ОСНОВНЫЕ ПОНЯТИЯ й 1.О. Некоторые предварительные пояснения П оя спим н некоторые термины и обозначения — общеов, — пот ебляемые математические и из теории графов, — употр в литературе не всегда одинаковым образом.

О ие «быть подмножеством» обозначается симтношен ':- В дс А В. волом =. Запись А с В означает А:— Пустое множество обозначается 8. Множество всевозможных упорядоченных пар элементов множества М обозначается '. Множество всех подмножеств М обозначается 2ы. Мощность множества М обозначается р(М). Операции алгебры логики и кванторы обозначаются дс, Ч, 1, :з, †= , тг, =[ соответственно. Если — отношение эквивалентности на множестве М, то множество классов, на котор р р ели р — отно то ые взбивает М, с ч актор-множеством множества , называется по отношению р и обозначается М/р. ощность р зывается и н д е к с о м отношения р. М ножество М с заданными на нем предикатами Р .

Во всех Рь ..., Р обозначается (М; Рь ..., Р„. остальных случаях упорядоченная си я система объектов иь ..., Йь обозначается альтернативно через (Жь ... Множество М с заданным на нем двуместным предикато (б рным отношением) В называется графом а ом инарн н обозначается, в соответствии с вышесказанн Вместо А'(а, Ь) пишем аРЬ, Элементы множества М ЦЕПОЧКИ И ЯЗЫКИ й [.и [гл. ОснОВные понятия [й называются у з л а м и графа (М; >с) "). Пара узло (а, Ь), для которой имеет место а>СЬ, называется ду гой графа; а есть начало этой дуги, Ь вЂ” ее конец Вместо <пара (а, Ь) является дугой» говорим «из а в Ь. идет дуга» или «а подчиняет Ь».

Последовательность узлов графа ае, аь ..., а„(п ) О) называется путем (идущим) из ие в а„в этом графе, если для ка>кдог 1= 1, ..., а из ас [ в а; идет дуга; а, есть начал пути, а„— его конец; число п есть длин а пути. Если из а в Ь идет путь, говорим, что Ь зависит от а. (В частности, всякий узел зависит от себя.) Узлы графа, не являющиеся началами никаких дуг, называются висячими, узлы, не являющиеся ни началами, ни концами никаких дуг, — и з о л и р о в а ни ы м и. Конечный граф называется д е р е в о м, если: а) в нем существует единственный узел (называемый корне.м), который не является концом никакой дуги; б) всякий. его узел, отличный от корня, является концом точно одной дуги; в) в нем нет замкнутых путей (т.

е. путей, концы которых совпадают с началами) ненулевой длины. Легко видеть, что в каждый узел дерева идет в точности один путь из корня. Множество всех узлов дерева, подчиненных одному узлу а, называется кустом этого узла, а множество, всех узлов, зависящих от а,— группой зависимое т и узла а. Число элементов куста называется его ш иринойой. Наибольшее значение ширины куста узла деб рева называется шириной дер ев а. Дерево называется б и н а р н ы м„если ширина куста каждого его невнсячего узла равна двум. В ы сотой, р а н гом и с т е п е н ь ю узла дерева называются соответственно длина пути из корня в данный узел, наибольшая длина пути из данного узла в висячий и наименьшая длина пути из данного узла в висячий.