Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Хомский Н. -> "Формальные свойства грамматик " -> 11

Формальные свойства грамматик - Хомский Н.

Хомский Н. Формальные свойства грамматик — Москва, 1963. — 100 c.
Скачать (прямая ссылка): formalsvoystvagrammatik1963.djvu
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 45 >> Следующая


Что касается раздела (а) теоремы, то очевидно, что автомат без Контроля допускает язык L1- \апЬ"\ (ср. с разд. 3 предыдущей
Формальные свойства грамматик

145

главы), но не допускает ни языка L2, ни языка L2'. Действительно, эти языки находятся за пределами возможностей любого устройства с конечным числом бесконечных счетчиков, показания которых независимы и изменяются фиксированным образом при переходах устройства из состояния в состояние (например, счетчик может показывать, сколько раз устройство прошло через данное состояние или произвело данный символ), причем решение о допущении или недопущении входной цепочки зависит от элементарных свойств показаний счетчиков (равны ли их показания; стоят ли они на нуле, как в случае магазинной памяти, и т.п.). Хотя устройство с q счетчиками и k состояниями имеет потенциально бесконечную память, за р шагов оно может достигнуть только kpq различных конфигураций состояния н показаний счетчиков, а при прохождении предложений языка Li, имеющих длину 2р, необходимо, чтобы за р переходов можно было достигнуть 2Р различных конфигураций (возможность пустых переходов не влияет на это замечание). Точную формулировку вышеописанных рассуждений и описание счетчико-вых устройств можно найти у Шюценберже [601.

Раздел (б) теоремы 4 есть следствие некоторых результатов, которые будут установлены ниже (разд. 1.6, теорема 6).

1.5. Конечные преобразователи

Допустим, что имеется устройство PDS М, удовлетворяющее дополнительному условию, что его лента памяти никогда не движется вправо, т.е. каждое правило M имеет вид (a, St, b)-±(Sj, х), где хфа. Начиная с начальной конфигурации, когда входная лента содержит последовательно символы #, ар,,...,а^, #, устройство работает в соответствии со своей программой, двигая ленту памяти влево каждый раз, когда оно печатает на этой ленте цепочку х. Предположим, что работа устройства продолжается до тех пор, пока оно не достигнет ситуации (#,S;, at ) для каких-то І, /, т.е. что оно блокируется точно в тот момент, как прочтет всю входную последовательность. На заключительном этапе леита памяти содержит некоторую цепочку y=wa] ,и мы говорим, что устройство M преобразует цепочку а^,...,а^п в цепочку у. Будем называть устройство M преобразователем, который отображает входные цепочки на выходные и соответственно входные языки на выходные. Обозначим через M(L) множество таких цепочек у, что для некоторого x?L M преобразует х в у. Заметим, что преобразователь никогда не достигает конфигурации, при которой он видел бы # на ленте памяти. Следовательно, он никогда не может «допустить» входную цепочку в ранее определенном смысле. В случае преобразователя лента памяти должна рассматриваться как выходная лента.

В случае преобразователя ограничения на формулу правил автомата PDS, касающиеся возврата в S0, очевидно, не понадобятся.

!/а 11 Заказ № 563
IS

И. Хомский

В самом деле, можно допустить, что правило / преобразователя имеет вид (a, S1, b)-*(Sj, х) [как в (1)], где а ? At, b ? A0 их есть цепочка в алфавите Ao— (о) , опуская дальнейшие ограничения.

Очевидно, что лента памяти преобразователя M не оказывает существенного влияния на течение его работы; и действительно, можно построить устройство Т, которое выполняло бы то же самое преобразование, что и M1 и при этом удовлетворяло бы дополнительному ограничению, что следующее состояние определяется только входным символом и настоящим состоянием. Состояния T записываются в виде (Sil а), где S1 —состояние М, a афе— символ его выходного алфавита. Начальное состояние T есть (S0, о). Если M имело команду (a, S1, b)-+(Sj , х), T будет иметь команду

[a, (S1, Ь), Ь\ -*¦ [(S,. с), х], (4)

где либо X=I{С, либо х=е и с=Ь. Поведение Т, очевидно, ничем не отличается от поведения М, но у T следующий шаг работы зависит только от входного символа и настоящего состояния, т.е. T представляет собой устройство PDS без контроля. Выбрасывая ненужное указание на символ, считываемый с ленты памяти, можно придать правилам T вид

(a, Ei) -> (Ех), (5)

указывающий, что когда T находится в состоянии Ei и наблюдает символ а (если афе) или не наблюдает никакого символа (если а—е) на входной ленте, оио может перейти в состояние E^, продвинуть входную ленту на X (а) клеток влево, а ленту памяти на Цх) клеток влево, записывая х на вновь открывшихся клетках ленты (если они имеются). Каждый преобразователь можно полностью описать диаграммой состояний, на которой узлы представляют состояния, а стрелка с надписью (а, х) ведет из состояния Ei в Е, тогда и только тогда, когда правило (5) есть одно из правил работы устройства.

Предположим, что на диаграмме состояний, представляющей преобразователь М, невозможно пройти по замкнутому пути, начиная и кончая фиксированным узлом, если идти только по стрелкам с пометкой (е, х) для некоторого х. Точнее говоря, пусть не существует такой последовательности состояний (Stl,,...,S4) устройства М, что <*!=<**, и для каждого i<k существует X1, такая, что (?. Sa()->-(Sai+l, Xi) есть правило Al. Если это условие выполнено, то число выходных цепочек, в которые может быть преобразована данная входная цепочка, ограничено, и такое M называется ограниченным преобразователем.
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 45 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed