Простая грамматика

Грамматики (подмножества множества слов в некотором алфавите ) можно описывать с помощью правил

  s -> 0
  s -> 1 s
  s -> 2 s s
  s -> 3 s s s 

Правило s -> 3 s s s , к примеру, означает, что если A, B и C являются корректными словами (принадлежат грамматике), то и слово "3 A B C" тоже является корректным (пробелы не считаются).

Примеры корректных слов: 0, 10, 110, 200, 2100, 2010.

Примеры не корректных слов: 01, 00, 300.

Приведённая ниже программа на С определяет корректность введённого слова.

#include <stdio.h>
#include <limits.h>

int
Read()
{
   int head,i;
    scanf("%d", &head);
    if(head < 0 || head > 3)
       return 1;
    for(i = 0; i < head ; i++)
    {
       if(Read())
           return 1;
    }
    return 0;
}
int
main()
{
  if(!Read())
  {  
    int tmp;
     if(!scanf("%d",&tmp))
        printf("in");
     printf("correct\n");
  }
  else
     printf("incorrect\n");
  return 0;   
}

-- ArtemVoroztsov - 09 Sep 2005