Грамматики (подмножества множества слов в некотором алфавите ) можно описывать с помощью правил. Каждое правило состоит из левой и правой части, между которыми стоит стрелка ( -> ).
Данную стрелку можно интерпретировать как «представляет собой» или «состоит из». Например, правило

A -> B C D
можно прочитать как

«Слово типа A представляет собой слияние слова типа B, слова типа C и слова типа D.»
Но в теории формальных грамматик принята другая терминология:

«Из символа A можно вывести последовательность символов B, C и D.»
Расcмотрим три правила, в которых присутствует только один символ S (один нетерминальный символ), и три терминальных (то есть нераскладываемых, таких символов, из которых ничего нельзя вывести кроме их самих) символов '0', '1', '2', '3':

S -> '0'
S -> '1' S
S -> '2' S S
S -> '3' S S S
Правило S -> '3' S S S , к примеру, означает, что если a, b и c являются корректными словами (словами, выводимыми из символа S), то и слово 3abc тоже является корректным.

Примеры корректных слов: 0, 10, 110, 200, 2100, 2010, 1111111110.
Примеры некорректных слов: 01, 00, 300, 3333, 11120.
Приведённая ниже программа на Си определяет корректность введённого слова.

 
  
 #include <stdio.h> 
 #include <limits.h> 
 int Read() 
 { 
 int head, i; 
 scanf("%d", &head); // Читаем первое число. 
 if(head < 0 || head > 3) { // Возвращаем код ошибки, если оно не из 
 return 1; // множества {0, 1, 2, 3} 
 } 
 for(i = 0; i < head ; i++) { 
 if(Read()) { 
 return 1; 
 } 
 } 
 return 0; 
 } 
 int main() 
 { 
 if(!Read()) { 
 int n; 
 if(scanf("%d", &n) != 0) 
 printf("incorect\n"); 
 else 
 printf("correct\n"); 
 } else { 
 printf("incorrect\n"); 
 } 
 return 0; 
 } 
 




---