Обзор способов представления контекстно-свободных грамматик и выбор наилучшего способа представления для использования в генетическом программировании
Иванов Сергей Викторович,
аспирант Саратовского государственного технического университета им. Гагарина Ю. А.
Научный руководитель – Ивженко Сергей Петрович.
В случае применения эволюционного подхода с использованием техники генетического программирования основным является способ кодирования программы в виде хромосомы. В случае генерирования грамматики роль программы, которая подлежит эволюции, выполняет продукция грамматики. Основные формы репрезентации продукции грамматики:
· нормальная форма Хомского (CNF);
· нормальный вид Грейбаха (GNF);
· вид Бакуса-Наура (BNF).
Нормальная форма Хомского (CNF)
Грамматика находится в нормальной форме Хомского, если все её продукции имеют вид:
или 
или 
,
где
A, B, C –
нетерминалы, 
– терминальный символ, 
– начальный
символ и 
– пустая строка. B и C не могут являться начальными
символами.
Каждая грамматика в нормальной форме Хомского является контекстно-свободной, и наоборот, каждая контекстно-свободная грамматика может быть преобразована в эквивалентную грамматику в нормальной форме Хомского.
За исключением
возможного правила , (используемого, когда грамматика может порождать пустую
строку), все правила грамматики в нормальной форме Хомского неукорачивающие; то
есть, в процессе вывода строки каждая цепочка из терминалов и нетерминалов
всегда имеет либо ту же длину, что и предыдущая, либо на один элемент больше.
Вывод строки длины 
всегда занимает ровно 
шагов. Кроме того, так как все правила вывода
нетерминалов переводят один нетерминал ровно в один терминал или ровно в два
нетерминала, дерево разбора, основанное на грамматике в нормальной форме
Хомского, представляет собой бинарное дерево, высота которого ограничена длиной
строки.
Благодаря этим свойствам, многие доказательства в теории формальных языков и вычислимости используют нормальную форму Хомского. Эти свойства также служат основой различных эффективных алгоритмов, например CYK-алгоритм, определяющий, может ли данная строка порождаться данной грамматикой, использует нормальную форму Хомского.
Нормальная форма Хомского названа по имени Ноама Хомского, американского лингвиста, предложившего иерархию Хомского [1].
Нормальная форма Грейбах (GNF)
Носит имя исследователя Ш. Грейбах, предложившего эту нормальную форму [2].
Контекстно-свободная грамматика находится в нормальной форме Грейбах, если любая продукция данной грамматики имеет следующий вид:
,
где 
- множество терминалов, 
- множество нетерминалов.
Пример грамматики в нормальной форме Грейбах:
Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Грейбах.
Форма Бакуса-Наура (BNF)
Форма Бакуса-Наура BNF является наиболее общей из представленных, что, как правило, позволяет выполнять запись грамматики с помощью меньшего количества продукций и нетерминальных символов, чем в случае применения записи в виде CNF или GNF. Уменьшение количества продукций и нетерминальных символов в записи грамматики непосредственно влияет на уменьшение области поиска [3].
Чтобы закодировать продукцию грамматики
в виде хромосомы, целесообразно представление грамматики в виде дерева. В таком
дереве корень представляет стартовый символ грамматики (
), а вершины –
символы, терминальные и нетерминальные, причем терминальные символы
представлены как листья дерева.
На рисунке 1 изображено представление контекстно-свободной грамматики с помощью дерева, а также соответствующая ей репрезентация в виде BNF.
Рис. 1. Пример представления контекстно-свободной грамматики: а) с помощью дерева; b) в виде BNF.
Далее приведен метод, состоящий в представлении дерева на круговой сетке.[4] Это метод позволяет представить структуру дерева с разветвленной сетью элементов, на относительно небольшой поверхности рисунка.
На рис. 2 в качестве примера показано дерево высоты 3, а также его представление с помощью круговой сетки.
Рис. 2. Представление дерева: a) стандартный способ; b) с помощью круговой сетки.
Метод представления дерева на круговой сетке применяется с целью представления его структуры, для которой не являются существенными отдельные вершины, поэтому вершины не берутся во внимание, а представляются только как структура связей элементов дерева.
На рисунке 3 приведен пример дерева, представляющего собой продукцию устойчивой грамматики (а), его представление на круговой сетке с обозначением вершин и краев (b) а также структуры связи элементов (c).
Рис. 3. Представление дерева: a) стандартным способом; b) с помощью круговой сетки; c) структуры связей элементов дерева с помощью круговой сетки без учета отдельных вершин.
Такое представление грамматик оправдано, например, при представлении результатов воздействия оператора мутации на отдельные грамматики, являющиеся потенциальными решениями при работе генетического алгоритма. Такое представление позволяет наглядно показать степень разрастания дерева, т.е. увеличение количества продукций грамматики, что является отрицательной характеристикой грамматики при ее оценке, как потенциального решения. Ниже приведен пример представления грамматик в виде деревьев и результат работы оператора мутации типа «делеция».
Рис. 4. Структура деревьев, представляющих выводы грамматик в последнем поколении для эволюции с применением оператора делеции.
Литература
1. Сайпсер М. Введение в теорию Исчислений / М. Спайсер.- PWS Publishing, 1997.- ISBN 0-534-94728-X.- 98-101 с.- раздел 2.1.
2. Грейбах Ш. Новая теорема о нормальной форме для контекстно-свободных грамматик / Ш. Грейбах - Journal of the ACM 12, 1965.
3. Вьярд П. Проблемы представления для вывода контекстно-свободных грамматик с использованием генетических алгоритмов / П. Вьярд,- ICGI `94 Материалы 2го международного коллоквиума о выводе и применении грамматик, 1994,- 222-235 с.
4. Визуализация структуры деревьев в генетическом программировании / Даида Дж. М., Хилсс А. М., Вард Д. Дж., Лонг С. Л., - 6, 2005, 79-110 с.
Поступила в редакцию 24.09.2014 г.