Материалы по курсу
"Формальные языки и грамматики"

Примеры задач для экзамена

1. Выписать однозначную КС-грамматику для следующих языков.
   1. Язык всевозможных описаний переменной "a" языка C, включающих операции определения указателя *, массива неопределенного размера [] и круглые скобки, используемые для группировки. Базовый тип -- int или char. Примеры цепочек языка:

        int *a;
        char *(*a)[];
        int a;
        int a[][];
        

   2. Язык правильных расстановок круглых скобок. Примеры цепочек языка:

        ()
        ()()
        (()())(())
        

   3. Язык логических выражений языка C, элементарное выражение обозначается буквой "e". Примеры цепочек языка:

        e && e
        e || e
        !e
        (!e && e) || (e && !e)
        

   4. Язык выражений языка C, включающий побитовые операции &, |, ~, ^ и скобки. Примеры

        e & e
        e | e
        e ^ e
        ~e
        (e ^ (~e & e)) | e
        

   5. Язык всех слов в алфавите {a, b}, в которых число букв "a" равно числу букв "b".
   6. Язык всех слов в алфавите {a, b}, в которых число букв "a" четно, а число букв "b" нечетно.
2. По данному недетерминированному конечному автомату построить детерминированный конечный автомат, задающий тот же самый язык.
   1.  
   2.  
   3.  
   4.  
3. По данному регулярному выражению построить конечный автомат (можно недетерминированный), задающий тот же самый язык.

   1.   ((ab|c)*|da)*ab
        

   2.   ab(c|d)*|(e|f)*)cd
        

   3.   ab*(a(c|d))*|ef*
        

4. По данному конечному автомату выписать регулярное выражение, задающее тот же самый язык.
   1.  
   2.  
   3.  
5. Выписать систему состояний LR(0)-разбора для заданной контекстно-свободной грамматики и определить, содержатся ли в ней конфликты.

   1.   S -> F
        F -> () | (F)
        

   2.   S -> F
        F -> a | *F
        

   3.   S -> F
        F -> a | F,a
        

   4.   S -> F
        F -> a | a,F
        

6. Выписать систему состояний LR(1)-разбора для заданной контекстно-свободной грамматики и определить, содержатся ли в ней конфликты.

   1.   S -> F
        F -> a | F,a
        

   2.   S -> F
        F -> a | a,F
        

   3.   S -> F
        F -> ε | aFa | bFb