Пример описания бесконтекстного языка с помощью бесконтекстного L-графа
Этот вид графов, назовем их бесконтекстными, отличается от регулярных тем,
что добавлен еще один вид пометок на дугах - скобки.
Скобки могут быть с индексами, т.е. разрешается несколько видов парных скобок.
Успешным путем, или маршрутом, в них считается такой путь, что последовательность его
скобочных пометок представляет собой сбалансированную скобочную систему.
Например, [1 [1 [2 ]2 [1 ]1 ]1 [3 ]3 ]1
является правильной скобочной системой, а
последовательности [ ] [, [ [ ], [1 [2 ]1 ]2 таковыми не являются. Разрешаются «нейтральные» дуги, не помеченные скобками.
Поэтому регулярный граф является частным случаем графа бесконтекстного.
