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

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

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


Как мы видели, если лента памяти в какой-то момент блокируется, то она остается блокированной в течение всей работы устройства. Следовательно, если /' применено, то устройство M' не может достичь конфигурации, в которой лента памяти сводится к е
Формальные свойства грамматик

15І

Коротко говоря, M' делает предположение, что после «стирания» ak+a, перейдя в конфигурацию Ks, устройство M будет наблюдать на ленте памяти символ аг. Исходя из этого, оно пишет a'ka',а, на своей ленте памяти, так что оно теперь тоже наблюдает на ленте памяти аг, «стерев» при этом и ak (знаком a'k), и о, (знаком а',). Если предположение было правильным, то новая конфигурация M' согласована с Ki, если оно было неверно, то лента памяти M1 блокирована и работа M никогда ие закончится с лентой памяти,, содержащей цепочку, которая сводится к е.

Ho M и M' имеют идентичные начальные конфигурации, если они имеют идентичные входные ленты. Следовательно, если M допускает х, то возможно, что M' будет работать, начиная из своей начальной конфигурации с входом х, и закончит работу в ситуации (#, S0, я') с цепочкой у иа ленте памяти, которая сводится к е. А если M не допускаете, то никакой возможный процесс работы M' из его начальной конфигурации с цепочкой х на входной ленте не может закончиться в ситуации (#, Sj-, а) для некоторого а с цепочкой, сводящейся к е в качестве содержимого ленты памяти. (Заметим, что содержимое ленты памяти в M' может быть сведено к е тогда и только тогда, когда M' напечатало о' и вернулось в S0 по правилу, аналогичному 7.)

Заметим также, что M' есть устройство PDS, которое никогда не сдвигает свою ленту памяти вправо (никогда не «стирает»). Мы уже показали в разд. 1.5, как в соответствии с каждым устройством такого рода мы можем построить эквивалентный преобразователь, который работает независимо от содержимого своей ленты памяти. Пусть T — преобразователь, построенный из M' таким способом, как это описано в разд. 1.5. Тогда M допускает* тогда и только тогда, когда T преобразует* в цепочку у, которая сводится ке.

Таким образом, мы имеем следующий общий результат.

T еорема 5. Если задано устройство PDS М, то можно построить преобразователь Т, такой, что M допускает х тогда и только тогда, когда T преобразует х в цепочку у, сводящуюся к е.

Предположим теперь, что L (M) — язык, допускаемый устройством FDS, обозначенным через М; T — соответствующий преобразователь, существование которого гарантируется теоремой 5; /С — множество цепочек в выходном алфавите T, которые сводятся к е; Ui— множество всех цепочек в выходном алфавите T и T'— обратный преобразователь, который отображает х на у в случае, если T отображает у на х. Тогда L(M)=T’(K П T(Ui)). Ho Ui- регулярный языки, как мы заметили в разд. 1.5, из этого следует, что T(Ui) тоже регулярный язык. Легко также показать, что К— бесконтекстный ягык (см. разд. 4 предыдущей главы).

10*
!52

И. Хомский

В разд. 4.6 мы покажем, что пересечение бесконтекстного языка и регулярного языка является бесконтекстным языком и что конечный преобразователь переводит бесконтекстный язык в другой бесконтекстный язык. Поэтому L(M) есть бесконтекстный язык.

В теореме 17 разд. 4.2 мы увидим, что для каждого бесконтекстного языка существует порождающее его устройство PDS с огра-ниченным контролем (см. разд. 1.4). Из этих результатов мы можем заключить следующее.

Теорема 6. Следующие три положения эквивалентны:

а) L допускается Некоторым, устройством PDS;

б) L допускается некоторым устройством PDS с ограниченным контролем [см. теорему 4 (6)1;

в) L —бесконтекстный язык.

1.7. Другие виды ограниченно-бесконечных'автоматов

Область ограниченно-бесконечных автоматов имеет огромный потенциальный интерес не только для теории порождающих процессов, но также, по-видимому, и для психологии, так как релевантные психологические модели, представляющие знание и способности организма, как можно ожидать, не будут ни строго конечными, ни неограниченно-бесконечными в смысле устройств, изучением которых мы займемся в разд. 1.8. Однако исследование этой области было предпринято совсем недавно, и известны пока лишь немногие начальные результаты. Ритчи [54] исследовал иерархию устройств, обладающих следующим общим свойством: на нижнем уровне иерархии находятся конечные автоматы, а на каждом следующем уровне объем памяти, находящийся в распоряжении устройства, является функцией длины входа, причем эта функция может быть вычислена устройством предыдущего уровня. Ямада [781 изучал случай автоматов «реального времени», которые подчинены условию, что допустимое число шагов работы определяется длиной входа (обзор некоторых его результатов см. в работе [451).

Шюценберже [65, 68] развил теорию конечных автоматов, снабженных множеством счетчиков, которые могут изменять состояния в соответствии с простыми арифметическими условиями на каждом шаге работы. Он [63 ] также связал некоторые из этих результатов с общей теорией бесконтекстных грамматик (см. разд. 4.7). Устройства, рассмотренные в разд. 2 и 3, являются ограниченно-бесконечными автоматами, и представляется разумным предсказать, что именно в этой форме математическое изучение грамматик, наконец, найдет свою естественную форму.
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 45 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed