Способы получения цепочек символов необходимы, чтобы формально дать определение языка L(G), описываемого заданной грамматикой G. Язык L(G) – это множество цепочек w терминальных (и только терминальных!) символов, выводимых из начального (стартового, главного) нетерминального символа S. L(G)={w|S?*w, где w – терминальные цепочки}.
Вертикальная черта после w в выражении означает, что w получены при условии, что они выводятся из S. А звездочка означает, что этот вывод может происходить за произвольное количество операций. При этом используется множество P правил, описанное в грамматике G.
Ниже приводятся примеры грамматики и описываемые ими языки.
Пример 1 G=(T,N,P,S).
T={x,y,w,z} – алфавит терминальных символов. Только эти символы можно использовать.
N={S,A,B} – множество нетерминальных символов, из которых S – главный (стартовый) нетерминальный символ. Именно с него должен начинаться вывод цепочек (слов) в соответствии с множеством правил вывода P.
Р={S®AB, A®x, A®y, B®w, B®z}.
Эти правила означают, что S можно заменить на последовательность нетерминальных символов AB. A®x, A®y означает, что А можно заменить на x или на y и т.д. Осуществляя эти замены, получаем цепочки w из терминальных символов, составляющих формальный язык L(G).
L(G)={xw, yw, xz, yz}.
Только эти четыре цепочки (слова) и составляют язык, описываемый заданной грамматикой G.