Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Отображение, осуществляемое преобразователем, назовем (конечным) преобразованием. Преобразование есть отображение цепочек на цепочки (и, следовательно, языков на языки) такого рода, что оно может быть выполнено строго конечным устройством.
Формальные свойства грамматик
147
Если дан ограниченный преобразователь Т, то можно, очевидно, отбросить сколько угодно команд вида (e,S,)-»(Sy, х), не изменяя осуществляемого преобразования, а просто позволив устройству при переходах из состояния в состояние печатать более длинные цепочки. И наоборот, добавив достаточное количество нигде более не употребляемых состояний и достаточно команд вида (5) с а=е, можно ддя каждого (не обязательно ограниченного) преобразователя T построить преобразователь T', осуществляющий то же отображение, что и T, но имеющий команды только вида (a, S1) -*¦ (Sj,b), где b ?Л0.
Заметим, что из существования такого преобразователя T' немедленно вытекает возможность построения «обратного» преобразователя T*, который отображает цепочку у на цепочку х тогда и только тогда, когда T отображает х на у. Для построения Т* достаточно просто поменять местами входные и выходные символы в командах Т'\ если, например, в команде вида (5) х есть символ из Ao, то надо поменять местами а их. Это сводится к замене каждой надписи (а, Ь) на стрелке диаграммы состояний надписью (Ь, а). Итак, для любого преобразователя T может быть построен обратный ему преобразователь T*, который отображает цепочку у на і тогда и только тогда, когда T отображает х на у, и который отображает язык L на множество всех таких цепочек х, что T отображает х на у ? L. Если T — ограниченный преобразователь, то Т* может и не быть ограниченным. Если обратный преобразователь T* также ограничен, то T называется преобразователем без потери информации. Общее исследование вопросов, относящихся к различным видам преобразователей, см. у Шюценберже и Хомского ([61, 691).
Эффект применения преобразователей к бесконтекстным языкам будет рассмотрен в разд. 4.5. Здесь отметим только, что если T преобразует язык Lb L' и L есть регулярный язык, то L' также будет регулярным языком. Известно также, что для каждого регулярного языка L существует преобразователь Tl, отображающий L на фиксированный язык U (а также такой, который отображает U на L), где U — множество всех цепочек в выходном алфавите (в обратном случае — во входном алфавите, причем если входной алфавит состоит только из одного символа е, то преобразователь по определению будет не ограниченным; в противном случае ои всегда может быть сделан ограниченным). Эти и некоторые другие связанные с этими факты становятся очевидными просто из рассмотрения диаграммы состояний.
1.6. Преобразование и автоматы PDS
Мы описали преобразователь в виде устройства PDS, которое никогда не сдвигает свою ленту памяти вправо, т.е. никогда не стирает — ни на каком шаге вычислений. Оно переводит входную V* П*
148
Н. Хомский
цепочку X в выходную цепочку у. С другой стороны общего вида устройство PDS использует свою ленту памяти для того, чтобы определить свои дальнейшие шаги, в частности окончательный допуск входной цепочки х. Оно заканчивает вычисление допущением х только тогда, когда при окончании содержание ленты памяти равно просто й, т.е. лента памяти пуста. Следовательно, мы можем представить себе общего вида устройство PDS преобразующим цепочки, которые оно получает, в пустую цепочку е, которая находится на ленте памяти, когда вычисление заканчивается допущением входной цепочки. (Устройство по существу представляет характеристическую функцию некоторого множества цепочек.) Мы намереваемся показать, как можно с каждым устройством PDS M связать преобразователь Т, построенный таким образом, что тогда н только тогда, когда M допускает х (т.е. преобразует ее в ё), T преобразует х в цепочку у, которая, в том смысле, как это мы определим, сводится к е1).
Предположим, что M есть устройство PDS с входным алфавитом Ai и выходным алфавитом Ao= {е, а2..........aq ).
Построим новое устройство M' с входным алфавитом Ai и выходным алфавитом Ao, содержащим 2q+l символов, где Ao = =Ao U {а'ь.,.,0:,'). Будем трактовать каждый элемент а{ в основном как «правый обратный» для а,. Более формально будем говорить, что цепочка х сводится к у в случае, когда имеется последовательность цепочек Z1,...,гт (m> 1), такая, что Z1-X, zm=y, и для каждого I-Cm имеются цепочки W1, W1 и Cipl ?Ао, такие, что Z1= = Wi a$t а'р( W1 и Zul=WlWl . Другими словами, х сводится к у, если х=у или если у мажет быть образована из х последовательным стиранием подцепочек Cij а/.
Мы говорим, что цепочка х блокирована, если x=yazat'w, где z сводится кеи либо уа сводится к е, либо а ?Ао— \е,Щ)- Если х блокирована, то для всех v, xv она блокирована и не сводится к е. Мы говорим, что лента памяти блокирована, если цепочка, которую она содержит, блокирована.
Новое устройство Ni' представляет собой автомат PDS, который никогда не сдвигает вправо свою ленту памяти. Оно будет построено таким образом, что если M не допускает х, то M' с х иа входе заканчивает работу либо прежде чем прочтет х, либо с блокированной лентой памяти; если же M допускает х, то M' будет работать так, что когда оно прочтет всю цепочку х, лента памяти не будет блокирована, т.е. ее содержание будет сводиться к е.
