Теория алгоритмов и формальных языков. Мелихов А.Н - 15 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Для данного ассоциативного исчисления проблема эквивалентности
разрешима, так кА любые два слова эквивалентны тогда и только тогда,
когда они обладают одним и тем же каноническим представителем, который
легко найти путем механически выполняемого процесса сокращения.
Однако проблема эквивалентности разрешима далеко не всегда.
Рассмотрим, например, тот же алфавит
},{ ваА
=
и соотношения ааа∼аа,
ава∼аа, вав∼вв, ввв∼вв. Из слова авава можно получить
аааааавааваава
≈
≈≈
или
авваавава ≈ . Слова аа и авва эквивалентны, несократимы, но различны.
Естественный метод решения проблемы эквивалентности слов,
сводящийся к перебору, состоит в следующем. Для произвольной пары слов
S и Т последовательно образуются все слова, смежные с S, потом все слова,
смежные с каждым из слов, полученных на первом шаге, и так далее. Короче
говоря, необходимо найти все слова, эквивалентные слову S, применяя
сначала одно, потом два, потом три преобразования и так далее, пока не
получится слово Т. Однако сколько бы преобразований не было выполнено,
тот факт, что Т не найдено, еще не означает, что оно не может быть получено
последующими преобразованиями. То есть указанный
метод не гарантирует
нахождения решения. Возникает вопрос: существует ли универсальный
метод, позволяющий решать проблему эквивалентности слова. В этом случае
эта проблема неразрешима. Мы вернемся к ней при рассмотрении машин
Тьюринга.
1.2. Комбинаторные системы
Комбинаторные системы - это частный случай формальных систем.
Они используются для исследования задач комбинаторного характера,
связанных с преобразованием
слов.
Для определения комбинаторной системы необходимо задать:
1) конечный алфавит А, называемый основным, и, возможно,
вспомогательный алфавит В. Из
ВА U образуется множество слов (формул);

Страницы