WWW.LIT.I-DOCX.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - различные публикации
 

«Операции над языками, генерируемыми n -грамматиками Commentationes Mathematicae Universitatis Carolinae, Vol. 15 (1974), No. 2, 211220 Persistent URL: Terms of use: © ...»

Commentationes Mathematicae Universitatis Carolinae

Viktor Alad'ev

Операции над языками, генерируемыми n -грамматиками

Commentationes Mathematicae Universitatis Carolinae, Vol. 15 (1974), No. 2, 211--220

Persistent URL: http://dml.cz/dmlcz/105547

Terms of use:

© Charles University in Prague, Faculty of Mathematics and Physics, 1974

Institute of Mathematics of the Academy of Sciences of the Czech Republic provides access to

digitized documents strictly for personal use. Each copy of any part of this document must contain these Terms of use .

This paper has been digitized, optimized for electronic delivery and stamped with digital signature within the project DML-CZ: The Czech Digital Mathematics Library http://project.dml.cz Соттеп"Ьа*Ыопе8 Ма1Ьен1а1;2сае Ша.тгег811;а"Ь18 СагоНпае 15,2 (1974)

ОПЕРАЦИИ НАД ЯЗЫКАМИ, ГЕВЖРЖРУЕШЫШ К^ -ГРАММАТИКАШ

Виктор АЛАДЬЕВ, Таллин Резюме: В настоящей с т а т ь е показывается, что языки, г е ­ нерируемые ^/^-грамматиками- незамкнуты относительно основ­ ных операций за исключением операции обращения .

Ключевые с л о в а : Однородная структура; слово, генерируе­ мое однородной структурой! ^т.—грамматика; язык, генерируе­ мый ч*^-грамматикой! - -системы»

О АМЗ: 94А20, 68А30, 92А05 Е е *. 2* Ш.764.11 Теория однородных структур представляет большой интерее для вычислительной техники, математической биологии, а также как отдельная ветвь абстрактных автоматов С1 - 3 ] .

Впоследние годы наибольшее число работ (в том числе и настоящая) по­ свящается структурным и поведенческим аспектам теории. В р а ­ боте 14] на основе одномерных однородных структур мы опреде­ лили и изучили ряд свойств языков, генерируе­ Хь-грамматики мых такими грамматиками. ^ ^ - г р а м м а т и к и подобны грамматикам, введенная Линденмайером С5 3 (так называемые I* -системы). Оба типа грамматик были впервые введены с целью изучения и описа­ ния формальных правил функционирования развивашцихся биологи­ ческих систем. Однако эти грамматики представляют определенный интерес и для теории формальных языков. Такие грамматики обла­ дают тем свойством, что на каждом шаге в выводе перерабатыва­ е т с я каждый символ слова, с которым грамматика оперирует. Та*ким образом, "^-грамматики и Ь -системы подобны другим

- 211 грамматикам с параллельными правилами замещения [6 - 81, но параллелизм в первых выше, так как в т^-грамматиках и ^ системах каждый символ слова заменяется на каждом шаге выво­ да. Более того, г^-грамматики на формальном уровне описыва­ ют функциониравание однородных структур, на которых реализу­ ются вычислительные и логические устройства, асами структу­ ры весьма удобны в качестве технической базы для организации параллельной обработки информации [22. Известно [43, что класс всех языков, генерируемых ^.^грамматиками, является собст­ венным подклассом класса всех языков, порождаемых ^ -систе­ мами» Такое сужение связано с тем, что правила замещения в ^ -системах позволяют делать вставки любых поделов в любые / места перерабатываемых системой слов, тогда как Г т# -грамма­ тики допускают %тх только на концах слов. Более того, ^* грамматика является алгоритмом, тогда как ^ -системы есть, вообще говоря, исчисления. Известно С91, что языки, порождае­ мые ^ -системами, незанкнуты относительно всех основных опе­ раций: объединения, пересечения, дополнения, обращения, про­ изведения, итерации, гомоморфизма и конечного преобразования .





Возникает интересный вопрос сравнения степени влияния такого сужения %^-грамматик относительно I* -систем на замкнутость языков, генерируемых чг^-грамматиками, относительно основных операций. Для дальнейшего нам понадобится ряд понятий и опре­ делений .

Классическое понятие одномерной однородной структуры (ОС) состоит в следующем. Имеется связанное множество идентичных конечных автоматов Щура, помещенных в точки пространства Ъ (рис) .

–  –  –

С0 е С^ - начальное слово или аксиома, г** Ь, * - правила вывода .

А множество с 0 генерируемое такой грамматикой, будем на­ зывать 1+1%щ) ^языком.

От общеизвестных формальных грамматик Х^ --грамматики, также как и ^ -системы, отличаются двумя основными моментами:

а) отсутствием нетерминального словаря,

б) одновременным применением правил вывода ( 1 ) .

Будем говорить, что множество слов ? с С ^ является язы­ ком ЪСъ^,), если существует ^^—грамматика, генерирующая множество & ш В работе С43 мы доказали, что множество С^ не может быть ^ СЪ^) -языком .

Для ^С^ ^Л( )-языков обычным образом определяются! все ос­ новные операции» Только операция дополнения определяется от­ носительно множества С^. Если мы обозначим через ^ * класс языков, порождаемых ^ -системами, а через Ъ{*Ь^) класс язы­ ков, генерируемых ^^-грамматиками, то свойства языков по

–  –  –

В этой таблице единица обозначает замкнутость относи­ тельно соответствующей операции класса языков определенного типа, нуль - неэамкнутость* Иэ анализа приведенной таблицж, учитывая, что языки без нетерминальных символов оказывают чрезвычайно большое сопротивление замкнутости относительно основных операций над "языками ПОЗ* можно сделать вывод, что при прочих равных условиях отсутствие возможности вставки подслов в любом месте генерируемого слова в ^-грамматиках исключает семейство ^('^ / п,) -языков из семейства! языков антиДР1 .

Результат.® ао ыезамкнутости относительно основных опе­ раций Ь* -языков можно найти в работе С93* В работе [43 мм доказали незамкнутость операций 1, 2, 5 - 8 и замкнутость операции 4 (таблица). Здесь мы решим вопрос и относительно опершдии дополнения* Теорема* Класс ^ 0 е ^ ) «-языков незамкнут относительно до­ полнения .

Доказательство* Выше уже говорилось, что в случае ъ^'

–  –  –

не может быть ^(ът) -языком* Теорема полностью я'Сx\^1 доказана .

В заключение настоящей работы нам хотелось бы сформули­ ровать следующую гипотезу: Дополнение ^С"Ы^)-языка не может быть снова ^С^, п,) -языком. Многочисленные попытки опроверг­ нуть эту гипотезу так же как и доказать ее не дали пока ни­ какого результата, хотя, результатн исследований поведенчесгких свойств однородных структур склоняют все же в сторону ис­ тинности гипотеэы .

• Е19 « JI M T e p a T y p a til B* AJLAHBEBs K TeopMM OAHOPO.ZI.HHX CTpyKTyp, Tax*HH,197& .

–  –  –

3] ?. ALADYE?: Survey of research in the theory of homogeneous structures and their applications, Mathematical Biosciences 9 (to appear) .

[4] B. AJlAJXbEB: t^-rpa.MMaTKKM M noposg^aeMHe HMM HSHKM, Mafi.AK 3CCP,23(1974) .

C5] A. LINDENMAXER: Developmental systems without cellular interaction.Their languages and grammars, J .

Theoret.Biol.30(1971),455-484 .

C6] S. GREIBACH and J. HOPCROFT: Scattered context grammars, J.Comput.Syst.Sci.3(1969),323-347* C.7] B. NASH and R. COHEN: Parallel levelled grammars, Tenth IEEE Conf.Swit.Aut.Theory (1969),263-276 .

CS] ?* RAJLICH: Absolutely parallel grammars and two-way deterministic finite state transducers, Proc .

Third ACM Symp. Theory Computing (197--)»132-137* It] A. L33JD1NMAYEE and G. ROZEMBERG: Developmental systems and languages, Proc•Fourth ACM Symp.Theory Computing (1972),214-221 .

CIO].A. SALOMAA: On sentential forms of context-free grammars, Acta Informatica 2(1973),40-49 .

3CT0HCKH-t $xuLum B U M I|CF CCCP

TUJULMM

–  –  –

- 220 -






Похожие работы:

«Материалы к зачету по биологии. Шуваев Сергей. Свойства живого. Специфическая организация и упорядоченность. Единство химического состава. Клеточное строение всего живого . Целостность и дискретность. Обмен веществ и энергии. Все живые системы – открытые. Ассимиляция и дисс...»

«010202 I. Область техники Настоящее изобретение относится к устройствам и способам для удаления целевых агентов из образца. В частности, настоящее изобретение относится к удалению патогенов из биологических образцов. II. Уро...»

«ИЗУЧЕНИЕ ТЕМПЕРАТУРНОГО РЕЖИМА В КАГАТЕ САХАРНОЙ СВЕКЛЫ ПОД ПОЛИМЕРНЫМ УКРЫТИЕМ С АНТИМИКРОБНЫМИ СВОЙСТВАМИ Акснов Д.М., аспирант, Сапронов Н.М., канд. с.-х. наук, Морозов А.Н., канд. с.-х. наук ГНУ Российский научно-исследовательски...»

«87 Особенности определения отдельных биологически активных производных анилина в тонком слое обращенно-фазового сорбента Шорманов В.К.1, Андреева Ю.В.1, Сухомлинов Ю.А.1, Омельченко В.А.2 ГОУ ВПО "Курский государственный медицинский университет", Курск ЭКЦ УМВД России по Орловской области, Орел Поступила в редакц...»

«Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего образования "Шадринский государственный педагогический университет" Педагогический фак...»

«ОГЭ—2019 Г.И. Лернер БИОЛОГИЯ ТРЕНИРОВОЧНЫХ ВАРИАНТОВ ЭКЗАМЕНАЦИОННЫХ РАБОТ ДЛЯ ПОДГОТОВКИ К ОСНОВНОМУ ГОСУДАРСТВЕННОМУ ЭКЗАМЕНУ Москва Издательство АСТ УДК 373:57 ББК 28я721 Л49 Лернер, Георгий Исаакович. менационных работ для подгот ство АСТ, 2018.— 127...»

«Министерство сельского хозяйства РФ Федеральное государственное образовательное учреждение высшего профессионального образования "Мичуринский государственный аграрный университет" Кафедра биологии растений и селекции плодовых культур УТВЕРЖДЕНО протокол № 9 метод...»

«Феномен белковой наследственности, патологические и функциональные амилоиды н.с. СПбФ ИОГен РАН к.б.н. Рогоза Т.М. Центральная догма молекулярной биологии по Crick, 1958 с дополнением (Бондарев и др., 2012.) Вторичная структура белка -слои Отдельные аминокислоты -спираль Параллельная и антипараллельная укладка мон...»







 
2018 www.lit.i-docx.ru - «Бесплатная электронная библиотека - различные публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.