Теория формальных грамматик и автоматов

12 его синтаксической структуры - можно либо выделить в нём составляющие - группы слов, функционирующие как цельные синтаксические единицы, либо указать для каждого слова те слова, которые ему непосредственно подчинены (если такие есть). Так, в предложении «Ямщик сидит на облучке» (А. С. Пушкин) при описании по первому способу составляющими будут все предложение П, каждое его отдельное слово и группы слов A = сидит на облучке и B = на облучке (см. рис. 1.3; стрелки означают «непосредственное вложение»); описание по второму способу даёт схему, показанную на рис. 1.4. Возникающие при этом математические объекты называются системой составляющих (первый способ) и деревом синтаксического подчинения (второй способ). Рис. 1.3. Система составляющих предложения «Ямщик сидит на облучке» Рис. 1.4. Дерево синтаксического подчинения предложения «Ямщик сидит на облучке» Системы составляющих используются преимущественно в описаниях языков с жёстким порядком слов (примером является язык программирования), деревья подчинения - в описаниях языков со свободным порядком слов (в частности, русского), формально для каждого предложения можно построить много разных синтаксических структур любого из двух видов, но среди них только одна или несколько являются правильными. Учитывая, что нас интересуют в первую очередь формальные языки, которые характеризуются жестким порядком слов в предложении,