4 Блок-схема алгоритма машины, порождающей слова языка
БСА построена по SM, приведенной в пункте 2, 1, 2, 3, a1, a2, b1, b2 – обозначение распознавателей пустого символа и символов a, b.
– останов
БСА-машины при неправильной ситуации
на ленте.
5
Строка Ляпунова (СЛ)
представляет граф в виде слова, построенный
по определенным правилами, который
служит логическим «скелетом» программы.
СЛ является логической моделью записи
программы на любом процедурном языке
для однопроцессорной алгоритмической
машины.
На рисунке представлена строка Ляпунова для алгоритма порождения со структурой данных СТ.
Строка Ляпунова суть последовательность символов П, условий распознавателя, стрелок и специального символа . Она строится по следующим правилам:
«+» стрелка не показывается, за ней всегда идет программный блок или символ (безусловный переход);
«–» стрелка показывает переход на соответствующий программный блок;
после символа стрелка показывает безусловный переход на соответствующий программный блок.
6. Эквивалентные преобразования СЛ. Символы СЛ могут быть переставлены в любой последовательности, при этом сохраняется логическая структура графа БСА.
Д
алее
приведена «запутанная» строка Ляпунова
(местами поменялись П2
и П3).
7. Строка Маркова (СМ). Сложность алгоритма зависит от структур данных. Строка Маркова (СМ) получила свое название по имени Маркова, автора нормального алгоритма Маркова, где она была впервые использована. СМ обладает рядом свойств, которые позволяют строить очень простые порождающие и распознающие алгоритмы. Но реализация структуры данных типа СМ даже в языках программирования высокого уровня достаточно сложна. Реализация СМ должна удовлетворять некоторым условиям.
Свойства СМ, которые делают ее «резиновой» (растягивающейся/сжимающейся) при перестановках (заменах) фрагментов слов:
а) Растяжение СМ.
Правило подстановки такое, что (длина слова меньше длины слова ). При выполнении подстановки строка растягивается.
Например, x = aaSbb – слово, (SaSb) – правило.
Применение правила дает слово x = aaaSbbb.
б) Сжатие СМ.
Правило подстановки такое, что > .
Например, x = aaSbb – слово, (aSbS) – правило; применение правила дает слово x = aSb.
Пример SM, порождающей слова языка L=anbn, использующей структуру данных «строка Маркова» (СМ). Обратите внимание, как упрощается алгоритм по сравнению с аналогичным, но работающим со «строкой Тьюринга» (п. 2).
Рис.2. Граф SM и ЛСА для задачи порождения слов языка L=anbn на строке Маркова.
а) Машина состояний (SM).
Алфавит языка:
– вспомогательный символ.
Алфавит состояний
.
Алфавит внешних
событий:
– продолжать порождение,
– закончить порождение.
Правила:
;
.
б) Логическая структура алгоритма ЛСА.
П0 – начальный блок, на ленту СМ занесен символ «».
П1 – подстановка ( а b), Пk – подстановка ( аb).
Значение распознавателя ek = «+» – закончить порождение,
ek = «–» – продолжать порождение.
Граф алгоритма на СМ очевидно проще, чем граф алгоритма на СГ (см. рис. 1).