1 / 13 Next Page
Information
Show Menu
1 / 13 Next Page
Page Background

МАТЕМАТИКА

DOI: 10.18698/1812-3368-2016-2-3-15

УДК 519.7

К ВОПРОСУ ЧАСТИЧНОГО УГАДЫВАНИЯ ФОРМАЛЬНЫХ

ЯЗЫКОВ

Р.С. Исмагилов

,

А.А. Мастихина

МГТУ им. Н.Э. Баумана, Москва, Российская Федерация

e-mail:

anmast@bmstu.ru

Рассмотрены бесконечные цепочки символов некоторого алфавита, порожден-

ные размеченным ориентированным графом. Модифицировано понятие ча-

стичного угадывания. Изложены методы частичного угадывания для класса

языков, основанные на ином подходе к рассматриваемым задачам. Доказан

критерий и приведен конструктивный алгоритм угадывания. Сопоставлены

результаты, полученные в настоящей работе, с результатами, полученными

ранее. Изложение замкнуто в себе и использует лишь элементарные понятия,

связанные с графами и автоматами.

Ключевые слова

:

частичное угадывание, граф, автомат.

TO THE PROBLEM OF PARTIAL GUESSING OF FORMAL

LANGUAGES

R.S. Ismagilov

,

A.A. Mastikhina

Bauman Moscow State Technical University, Moscow, Russian Federation

e-mail:

anmast@bmstu.ru

The purpose of the study is to examine the infinite chains of symbols of an alphabet,

generated by a marked directional graph. The findings of the research helped us

to modify the notion of partial guessing. For a class of languages, we employed

methods of partial guessing based on a different approach to the problems under

consideration. We found a criterion and a constructive algorithm of guessing. We

compared the results obtained in this study with the results obtained previously. In

this research we present only basic concepts associated with graphs and automata.

Keywords

:

partial guessing, graph, automata.

Введение.

Задача угадывания может быть описана (в вольном изло-

жении) следующим образом. Имеется бесконечная цепочка символов

некоторого алфавита (сверхслово), порожденная некоторым механиз-

мом (в каждый момент времени поступает один символ). В качестве

такого механизма берутся размеченные ориентированные графы (ав-

томаты). Зная начало указанной цепочки, требуется предсказать (уга-

дать) следующий ее символ; разумеется, такое угадывание также вы-

полняется автоматом. Некоторые аспекты этой задачи рассмотрены в

работе [1]. Достаточно естественным представляется несколько “смяг-

чить” описанную “жесткую” постановку (угадать каждый символ

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2

3