Контрольная теория языков программирования

1. Показать, что данная грамматика
stmtIF expr THEN stmt | IF expr THEN stmt ELSE stmt | OTHER
не является однозначной.
2. Дана неоднозначная грамматика SaS | aSbS | e. Доказать, что для цепочки aab справедливо:
 существует два дерева разбора;
 цепочка имеет два левых порождения.
3. Грамматика порождает префиксные выражения с x,y, *,+,-
E +EE | *EE | -EE | x | y
Найти для цепочки +*-xyxy левое порождение и дерево разбора.
4. Построить детерминированный конечный автомат, допустимым для которого является язык L={w| w содержит четное число 0 и четное число 1}
5. Постройте НКА, принимающий язык Lk={Множество слов в алфавите {a,b}, у которых третий от конца символ равен «a»}. Затем, используя алгоритм, постройте соотв. полный ДКА.
...

1. Показать, что данная грамматика
stmtIF expr THEN stmt | IF expr THEN stmt ELSE stmt | OTHER
не является однозначной.
2. Дана неоднозначная грамматика SaS | aSbS | e. Доказать, что для цепочки aab справедливо:
 существует два дерева разбора;
 цепочка имеет два левых порождения.
3. Грамматика порождает префиксные выражения с x,y, *,+,-
E +EE | *EE | -EE | x | y
Найти для цепочки +*-xyxy левое порождение и дерево разбора.
4. Построить детерминированный конечный автомат, допустимым для которого является язык L={w| w содержит четное число 0 и четное число 1}
5. Постройте НКА, принимающий язык Lk={Множество слов в алфавите {a,b}, у которых третий от конца символ равен «a»}. Затем, используя алгоритм, постройте соотв. полный ДКА.

1. Показать, что данная грамматика
stmtIF expr THEN stmt | IF expr THEN stmt ELSE stmt | OTHER
не является однозначной.
2. Дана неоднозначная грамматика SaS | aSbS | e. Доказать, что для цепочки aab справедливо:
 существует два дерева разбора;
 цепочка имеет два левых порождения.
3. Грамматика порождает префиксные выражения с x,y, *,+,-
E +EE | *EE | -EE | x | y
Найти для цепочки +*-xyxy левое порождение и дерево разбора.
4. Построить детерминированный конечный автомат, допустимым для которого является язык L={w| w содержит четное число 0 и четное число 1}
5. Постройте НКА, принимающий язык Lk={Множество слов в алфавите {a,b}, у которых третий от конца символ равен «a»}. Затем, используя алгоритм, постройте соотв. полный ДКА.

G
4) Выделим достижимые состояния автомата
5) Построим детерминированный конечный автомат.
7) Зададим автомат в виде таблицы переходов
11
00
{S}
{S,R}
{Ø}
{S,R}
{S,R}
{R,Z}
*{R,Z}
{ Ø }
{R,Z}
Задача.
Постройте НКА, принимающий язык Lk={Множество слов в алфавите {a,b}, у которых третий от конца символ равен «a»}. Затем, используя алгоритм, постройте соотв. полный ДКА.
Решение:
Данному языку соответствует регулярное выражение:
(a|b)*a(a|b)(a|b)
Построим НКА
Функция переходов представлена следующим образом:
(A, a) ={A,B}, (A, b) ={A}, (B, a) ={C}, (C, a) ={D},
(B, b) ={C}, (C, b) ={D}.
Построим ДКА:
4) Построим булеан множества состояний (Q)
a
b
{Ø}
{Ø}
{Ø}
{A}
1
{A,B}
5
{A}
1
{B}
2
{C}
3
{C}
3
{C}
3
*D
4
*D
4
*{D}
4
{Ø}
{Ø}
{A,B}
5
{A,B,C}
11
{A,C}
6
{A,C}
6
*{A,B,D}
12
*{A,D}
8
{B,C}
7
*{C,D}
10
*{C,D}
10
*{A,D}
8
{A,B}
5
{A}
1
*{B,D}
9
{C}
3
{C}
3
*{C,D}
10
*D
4
*D
4
{A,B,C}
11
*{A,B,C,D}
14
*{A,C,D}