загрузка...
 
2. 5 Формальное определение языка
Повернутись до змісту

2. 5 Формальное определение языка

Способы получения цепочек символов необходимы, чтобы формально дать определение языка 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.



загрузка...