МАТЕМАТИКА
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.ruThe 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