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

Поэтому предположение о рекурсивностн, например, графика функции ?(Г,х) немедленно приводит к противоречию, так как из него вытекает существование алгоритма, позволяющего для любого и = 1, 2, ... узнать, выполняется ли равенство ?(Га,аз") = 2а, т. е. принадлежит ли число и множеству СМа. Впрочем, для некоторых важных классов грамматик индуцируемые операторами )(л, "уп, Р, 1 относительные операторы будут сигнализирующнми. В частности, зто сигнализнруюшив Функции. грамматик 59 имеет место для НС-грамматик (см. $3.3); именно ради пения к НС-грамматикам (в основном даже к Б- приме грамматикам, см. гл.

7) мы и рассматриваем у казанные операторы. Для произвольной грамматики Г = (У,)р,зг,,о), порождающей бесконечный язык, имеют место неравенства (1) Вг(п) ) шах(н, 1); Тг (л) )1; ?г(п) ..аРг(п)аб(?гл(и).ляг(и) адтг(н)+1, ?г (л) ( Рг (л) ( ф~~ (и) ( 5~ (и) ~ 4Тг (л) + 1; г(ю (3) Тг (л) ( Здесь д= гпах ) ) ф) — ) ср П н й — мощность множеф-ьв е я ства У () ЯУ. Неравенства (1) и (2) непосредственно следуют нз определени ад й ( ля получения последнего из неравенств (2) надо еще воспользоваться тем очевидным фактом, что ни на каком шаге вывода цепочка не может удлиниться более чем на д). (3) вытекает из леммы 1.3, поскольку для бесповторного вывода (юы ..., юя) такого, У 0 'У' лины, не числа различных цепочек в словаре , дли йз ы большей 1, а это число равно, 1 ° Отметим следующее свойство сигнализирующих, Л ем м а 2.1.

?(ля произвольной грамматики Г следующие утверждения равносильны: (1) язык Е(Г) ргкурсивгн; (2) любая сигнализирующая грамматики Г вычислима е); (3) любая сигнплизиругощая грамматики Г жорируется **) подходящей вычислимой 4ункциеи; (4) хотя бы одна сигнализирующая грамматики Г в мажори числима; (5) хотя бы одна сигнализирующая граммати- ') Поскольку сигиализирующая любой грамматики есть всюду определенная жун ц ф к ия, вьщислимость здесь и далее можно заменить общей рекурсивностью. ется ф нк*') Яы говорим, что функция я(а) м а ж о р и р у е т с я кунцией й(п), если для каждаго и, для котарого д(п) определена, й(п) также определена и я(п) ~ 6(й).

СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ Э 2.Я СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ, ГРАММАТИК Б! ]гл. т ки Г мажарируется вычислимай функцией При эхом па алгоритму, требуемому каким-либо одним из перечис- . ленных утверждений, можно построить алгоритмы, тре-, буемые остальными. Д о к а з а т е л ь с т в о. Достаточно доказать имплика- . ции (1):э (2) и (5) ~ (1). Пусть язык Е(Г) рекурси- .' вен и Рг (и) — какая-либо сигнализирующая Г. Для: произвольной цепочки х в основном словаре Г мы мо- жем узнать, принадлежит ли оиа Е(Г), и в случае поло- жительного ответа найти значение Р(Г,х), последова- тельно проверяя равенства Р(Г, х) = О, Р(Г, х) = 1 и т.

д. Таким образом, функция Р(Г, х) (с фиксирован- ной Г), а следовательно и Р(Г, и), оказывается вычис-:. лимой. Пусть теперь некоторая сигнализирующая Рг(п) грамматики Г мажорируется (всюду определенной) вы- 'числимой функцией Ь(п). Тогда для каждой цепочки х еи Е(Г) имеет место Р(Г, х) = Ь(]х]); в то же время при хфЕ(Г) функция Р(Г,х) ие определена. Поэтому х еи Е(Г) тогда и только тогда, когда выполняется хотя бы одно из равенств Р(Г,х) = О, ..., Р(Г,х) = Ь(]х]), а они поддаются проверке в силу рекурсивности графи- ка Р(Г,х). Заметим, что если для некоторого сигнализирующего оператора Р(Г, х), некоторой вычислимой функции Ь(п) и некоторого класса грамматик У имеет место Р(Г, п) ~ Ь( ~х~ ), какова бы ни была грамматика Ген У, то указанный только что метод доказательства импликации (5) ~ (1) дает единый алгоритм, позволяю- щий для любой грамматики Г~У и для любой цепоч- ки х в основном словаре этой грамматики распознать, принадлежит ли х языку Е(Г).

В дальнейшем нам будут полезны следующие обоз- начения. Пусть гс — некоторый класс грамматик, Р— квазисигнализирующий оператор и 3 — класс числовых Р функций. Тогда через сэ (У ) мы будем обозначать класс языков, порождаемых такими грамматиками клас- са У, у которых квазисигнализирующие типа Р мажори- руются какими-либо функциями класса о. Если 6 со- стоит из одной функции 1, будем вместо 2'з(У ) писать Р Р .'х"с (У ).

Кроме того, вместо 2'з (Г) (à — класс все» грамматик, см стр, ЭО) мы будем писать Ыэ, Наконец, Еьа(Г), где à — грамматика, Р— квазисигнализирующий оператор и Ь вЂ” натуральное число, будет означать множество цепочек х ~ Е(Г), удовлетворяющих условию Р(Г, х) ~ Ь. 3 а м е ч а н и е.

Обратившись к конструкции, примененной в доказательстве леммы 1.4, легко увидеть, что для фигурирующих там грамматик Г и Г' имеют место соотношения Бг.(п)=ЯГ(п), Тг (и) ..ЬТг(п), где Ь вЂ” постоянная, зависящая от Г (и допускающая эффективное вычисление). Действительно, если Р— полный вывод цепочки х в Г и Р' — соответствующий полный вывод х в Г', то максимальные длины цепочек в Р и в Р' совпадают, а длина самого вывода Р' равна сумме длины Р и длины х; но длина х ие превосходит длины Р, умноженной на максимум длин правых частей правил Г. Нам понадобится также Лемма 2.2.

Для произвольной грамматики Г можно построить эквивалентную ей грамматику Г', удовлетворяющую следующим условиям; а) Г' не имеет правил с пустой левой частью. б) Для любого полного вывода Р в Г, оканчивающегося цепочкой х, можно построить равносильный ему полный вывод Р' в Г', отличающийся ат Р только тем, чта на тех местах (кроме паследнега, если х = Л), на которых в Р стоит Л, в Р' стоит цепочка из одного символа Е, не встречающегося в остальных цепочках Р.

При этом Р' можно разметить так, чтабьс при х~ Л правьсе части всех применяемьсх правил бьсли непусты, а при х = Л правило с пустой правой частью применялась только на последнем шаге. Если Р— упарядачиваемьсй вывод, та Р' — такэке упарядачиваемый вывод. Обратна, любой вывод в Г' можно получить из некоторого вывода в Г указанным способам. в) 5г (и) = Зг(п); Тг (п) = Тг(п) Если Лей Е(Г), та можно сверх сказанного потребовать, чтабьс а') Г' не имела правил с пустой правой частью. Доказательство.

Пусть Г = ()А, В',Т,Р). Каждому правилу из ст вида Л-+ф соответственно ф- Л, СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ А КЗ] СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ МАШИН ТЬЮРИНГА ЕЗ сопоставим всевозможные правила а-Р аф и а- фа соответственно сир- а, ~и- и, где а ен )Г 0 Ж', а также правило Е- ф, соответственно ~р- Е, где Š— символ,- не входящий в )' () Я'. Присоединим к йт символ Е и к )à — все новые правила„одновременно удалим из )г все ' правила вида Л- ф. Полученная грамматика Г' удов- летворяет условию а). Выполнение условия б) легко ' проверяется непосредственно; условие в), равно как и эквивалентность Г и Г', следует из б).

Наконец, в силу а) и б) при Лф Ь(Г) из схемы Г' можно удалить пра- . вила вида ~р — Л, что дает а'). й 2.2. Сигнализирующие функции машин Тьюринга Пусть ) (М, С,1) — вычислимая функция, принимающая в качестве значений натуральные числа и определенная на всевозможных тройках (М, С, 1), где М— Э-машина, С= (зм зь ..., З„) — вычисление машины М и 1=, 1...,, а. (Алфавиты и множества состояний всех рассматриваемых машин считаем содержащимися в некотором множестве Е.) Для произвольной цепочки хан Е(М) и произвольного полного х-вычисления С = = (зм зь ..., З») машины М положим Т (М, С, х) = шах 1'(М, С, 1).

Для любой цепочки хан Е(М) положим Р(М, х) = пппг(М, С, л), где минимум берется по всем полным х-вычислениям машины М. Наконец, положим Р(М, п) = шах Р(М, к); для тех и, » ~щмк 1» ~ «л для которых не существует таких х ен Ь(Г), что (х) ( и, полагаем Р(М, и) = О.

Так определенную функцию Р(М,Н) мы будем называть квазисигнализирующим опер а то ом д -м а ш и н, а функцию Рм(а), получаемую из ля Э-. атором Р(М,Л) фиксированием М,— квазисигна лизи р ующей (функцией) типа Рмашины М. Если М вЂ” ДЭ-машина, то можно определить Рм(п) непосредственно как Гпах Т(М, С, х), поскольку в этом случае цепочка х ех Ь(М) имеет единственное полное вычисление. В случае, когда график функции Р(М, х) рекурсивен, мы будем называть соответствующий оператор Р(М,Л) сигнализирующнм оператором для Эмашин и функцию Рм(п) — сигнализирующей (функцией) типа Р м а шины М. Нас будут интересовать два типа сигнализирующих функций Э-машин: в р е м я р а б о т ы — обозначение Тм(п) — и емкость — обозначение 5м(л).

При определении этих функций в качестве 1(М, С, 1) берется соответственно число 1 и длина рабочей ленты в ситуации з~ (т. е. число ее ячеек, ие считая ячейки, занятой граничным маркером). Тот факт, что соответствующие операторы действительно являются сигналнзирующими, устанавливается точно так же, как для грамматик ($2.1). Аналогично неравенствам (1), (2), (3) из $2.1 нетрудно получить следующие неравенства (доказательство предоставляется читателю): (1') Тм(а) и+ 1, (2') Бм(п) а 1(ТМ(п)-(и+ 1)), зм еею+~ (3') Тм(п) ( Г(и+ 1)(Ям (и)+1) где й, à — мощности рабочего алфавита и множества состояний машины М соответственно. В главе 1 (теорема !.2) мы доказали, что для каждой Э-машины М можно построить ДЭ-машину М, такую, что Е(М,) = Ь(М).