Теория формальных грамматик, Гросс М., Лантен А, 1971.
Фрагмент из книги.
«Универсальный» метод решения проблемы эквивалентности, который прежде всего приходит в голову, состоит в следующем: взяв произвольную пару слов S и Г, последовательно образовать все слова, смежные с S, потом все слова, смежные с каждым из слов, полученных на первом шаге, и т. д., т. е., короче говоря, перечислить все слова, эквивалентные слову S, применяя сначала одно, потом два, потом три преобразования и т. д., пока мы не дойдем до Т. Однако сколько бы преобразований ни было выполнено, тот факт, что Т не найдено, еще ничего не означает: оно может быть получено после очередных преобразований. Таким образом, наш наивный «универсальный» метод не гарантирует нахождения решения.
Возникает вопрос: существует ли настоящий универсальный метод, позволяющий решать проблему эквивалентности слов? После того как мы уточним представление о методе решения вообще — точнее, введем понятие алгоритма, —можно будет показать, что ответ на этот вопрос является отрицательным.
