ТЕОРИЯ АВТОМАТОВ

 Задания контрольной работы, вопросы к экзамену и список литературы

 для студентов-заочников 3-го курса специальности «ВКСС»

Вариант № 1

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n-m – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C,D}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AB|CD, A->aAb|C|e, B->bBa|C|e, C->abSba|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ba и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->a|Ba, B->Bb|b}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p,q}	{q}
q	{s}	{s}
*r	{r}	Æ
s	{r}	{r}

7. Для данного РВ построить ДКА: 00(0+1)^*+11

8. Для данного ДКА исключить состояния q, s и построить РВ.

	0	1
->p	s	p
q	p	s
*r	r	q
s	q	r

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/1	1/1	2/1	1/1
1	3/0	3/0	4/1	3/1
2	1/1	2/1	1/0	2/0

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать T-триггер.

Вариант № 2

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n-m – нечетное число.

2.Задана формальная грамматика  G=<{a, b}, {S, A, B, C}, R,S>.  Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка. R={S->A|AS, A->abA|Ba|e, B->Bba|bC|e, C->bCa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку aa и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Ab, A->Aa|ba}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,s}	{q}
*q	{r}	{q,r}
*r	{s}	{p}
s	Æ	{p}

7. Для данного РВ построить ДКА

01^*+0^*1

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q2	q3
*q2	q1	q3
q3	q2	q1

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/0	4/0	2/0	3/0
1	3/0	3/1	1/0	2/1
2	1/1	2/1	3/1	4/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать D-триггер.

Вариант № 3

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb²aⁿ, где n – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без леворекурсивных правил.

R={S->BaA|SbB, A->Abb|aCa|e, B->bBa|e, C->bCa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку aa и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0A1|01, 0A->00A1, A->01}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,r}	{q}
q	{s}	{s,r}
*r	{r}	{p}
s	Æ	{p}

7.Для данного РВ построить ДКА

(00+11)^*

8.Для данного ДКА исключить состояние q₃  и построить РВ.

	0	1
-> q1	q2	q1
*q2	q3	q1
q3	q3	q2

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	2/1	4/1
1	3/0	3/1	1/1	3/0
2	4/1	2/1	3/1	1/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать R-S-триггер.

Вариант № 4

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb²aⁿ, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка. R={S->BA|bSB, A->baA|bCa|e, B->bSa|e, C->bAa|e}.
3. Получить множество строк, не более 4 знаков, содержащих подстроку ba и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->AB, AB->BA, A->a, B->b}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p}	{q}
*q	{s}	{s,r}
*r	{r,s}	{q,r}
s	Æ	{q}

7. Для данного РВ построить ДКА

1^*00^*(1+0)

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q3	q1
*q2	q2	q1
q3	q2	q3

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	4/1	4/1
1	3/1	3/0	2/0	1/1
2	4/1	1/1	1/1	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать J-K-триггер.

Вариант № 5

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид bⁿ⁺²aⁿ, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->CC|CS, A->baA|bBa|e, B->bAa|e, C->bSa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->A|B, A->aAb|0, B->aBbb|1}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,p}	{p}
q	{r,s}	{t}
r	{p,r}	{t}
*s	Æ	Æ
*t	Æ	Æ

7. Для данного РВ построить ДКА

1^*(0+1)^*0^*

8.Для данного ДКА исключить состояние q₂  и построить РВ.

	0	1
-> q1	q2	q3
q2	q1	q3
*q3	q2	q1

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	1/0	4/1	1/0
1	4/0	2/1	2/0	4/1
2	2/0	4/1	3/0	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать T-триггер.

Вариант № 6

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿ⁺²b^n-2, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AC|BA, A->baB|bAa|e, B->bSa|e, C->bBa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0A|1S, A->0A|1B, B->0B|1B|1}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{r,s}	{q}
*q	{p}	{q,p}
r	{s}	{p}
*s	{p}	Æ

7. Для данного РВ построить ДКА

0^*(0+1) 1^*

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q3	q2
*q2	q3	q1
q3	q1	q2

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	3/0	4/0	2/1	2/1
1	4/1	1/1	3/1	4/1
2	2/0	4/0	4/1	3/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать D-триггер.

Вариант № 7

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид (ab)ⁿ(bb)ⁿ, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AA|BB, A->bCa|bBa|e, B->bBa|e, C->bSa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0S|S0|D, D->DD|1A|e, A->0B|e, B->0A|0}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q}	{q,s}
*q	{q,r}	{r}
*r	{p}	{s}
s	{p}	Æ

7. Для данного РВ построить ДКА

00(00)^*+11(11)^*

8. Для данного ДКА исключить состояние q₂ и построить РВ.

	0	1
-> q1	q1	q2
q2	q2	q3
*q3	q3	q3

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/0	1/0	2/1	1/1
1	3/0	3/0	4/0	3/0
2	1/1	2/1	1/1	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать R-S -триггер.

Вариант № 8

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид (ab)ⁿ(bb)^m, где n, m – четные.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->A|B|ASB, A->bCa|bSa|e, B->bCa|e, C->bSa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0A|1S|e, A->1A|0B, B->0S|1B}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q}	{p,q}
q	{s}	{s}
*r	Æ	{r}
s	{r}	{r}

7.Для данного РВ построить ДКА

1^*0^*(0+1)1^*

8.Для данного ДКА исключить состояния r, s  и построить РВ.

	0	1
->p	s	p
*q	p	s
r	r	q
s	q	r

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/1	4/0	2/1	3/0
1	3/0	3/1	1/0	2/1
2	1/1	2/0	3/1	4/0

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать J-K -триггер.

Вариант № 9

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n+m – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->A|B|ASB, A->B|bCa|bSa|e, B->C|bCa|e, C->A|bSa|e}.

3. Определить, принадлежит ли строка a=abba языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->SS|A, A->a|bb}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p,q}	{q}
q	{s}	{s}
*r	{r}	Æ
s	{r}	{r}

7.Для данного РВ построить ДКА: 00(0+1)^*+11

8.Для данного ДКА исключить состояния q, s  и построить РВ.

	0	1
->p	s	p
q	p	s
*r	r	q
s	q	r

9. Для данного ДКА исключить состояния q, s и построить РВ.

	0	1
->p	s	p
q	p	s
*r	r	q
s	q	r

10.Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/1	1/1	2/1	1/1
1	3/0	3/0	4/1	3/1
2	1/1	2/1	1/0	2/0

13. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать T-триггер.

Вариант № 10

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n+m – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->С|ASB, A->С|bCa|bSa|e, B->S|bCa|e, C->A|bSa|e}.

3. Определить, принадлежит ли строка a=baab языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->AB, A->a|Ca, B->bA}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,s}	{q}
*q	{r}	{q,r}
*r	{s}	{p}
s	Æ	{p}

7. Для данного РВ построить ДКА

01^*+0^*1

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q2	q3
*q2	q1	q3
q3	q2	q1

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/0	4/0	2/0	3/0
1	3/0	3/1	1/0	2/1
2	1/1	2/1	3/1	4/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать D-триггер.

Вариант №  11

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n-m – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->С|A|B, A->S|bCa|e, B->S|bCa|e, C->B|bSa|e}.

3. Определить, принадлежит ли строка a=baab языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Aba|e, B->bSA, AA->c}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,r}	{q}
q	{s}	{s,r}
*r	{r}	{p}
s	Æ	{p}

7.Для данного РВ построить ДКА

(00+11)^*

8.Для данного ДКА исключить состояние q₃  и построить РВ.

	0	1
-> q1	q2	q1
*q2	q3	q1
q3	q3	q2

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	2/1	4/1
1	3/0	3/1	1/1	3/0
2	4/1	2/1	3/1	1/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать R-S -триггер.

Вариант № 12

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n-m – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->С|A|B, A->S|bCa|e, B->A|bCa|e, C->B|bSa|e}.

3. Определить, принадлежит ли строка a=aaab языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Ab|c, A->Ba, B->cS}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p}	{q}
*q	{s}	{s,r}
*r	{r,s}	{q,r}
s	Æ	{q}

7. Для данного РВ построить ДКА

1^*00^*(1+0)

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q3	q1
*q2	q2	q1
q3	q2	q3

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	4/1	4/1
1	3/1	3/0	2/0	1/1
2	4/1	1/1	1/1	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать J-K -триггер.

Вариант № 13

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^ma^m, где n-m – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->СA|A, A->S|C|baA|e, B->A|bCa|e, C->S|bSa|e}.

3. Определить, принадлежит ли строка a=bbaa языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Ab, A->Aa|ba}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,p}	{p}
q	{r,s}	{t}
r	{p,r}	{t}
*s	Æ	Æ
*t	Æ	Æ

7. Для данного РВ построить ДКА

1^*(0+1)^*0^*

8.Для данного ДКА исключить состояние q₂  и построить РВ.

	0	1
-> q1	q2	q3
q2	q1	q3
*q3	q2	q1

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	1/0	4/1	1/0
1	4/0	2/1	2/0	4/1
2	2/0	4/1	3/0	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать T-триггер.

Вариант № 14

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид bⁿb^ma^m, где n-m – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->A|B, A->B|C|baA|e, B->S|bCa|e, C->A|bSa|e}.

3. Определить, принадлежит ли строка a=aabb языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Ab, A->Aa|ba}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{r,s}	{q}
*q	{p}	{q,p}
r	{s}	{p}
*s	{p}	Æ

7. Для данного РВ построить ДКА

0^*(0+1) 1^*

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q3	q2
*q2	q3	q1
q3	q1	q2

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	3/0	4/0	2/1	2/1
1	4/1	1/1	3/1	4/1
2	2/0	4/0	4/1	3/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать D-триггер.

Вариант № 15

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид (ab)ⁿ(ba)ⁿ, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AS|B, A->bSa|bBa|e, B->bCa|e, C->bCa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку bb и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->SS|A, A->a|bb}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q}	{q,s}
*q	{q,r}	{r}
*r	{p}	{s}
s	{p}	Æ

7. Для данного РВ построить ДКА

00(00)^*+11(11)^*

8. Для данного ДКА исключить состояние q₂ и построить РВ.

	0	1
-> q1	q1	q2
q2	q2	q3
*q3	q3	q3

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/0	1/0	2/1	1/1
1	3/0	3/0	4/0	3/0
2	1/1	2/1	1/1	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать R-S -триггер.

Вариант № 16

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид bⁿb^ma^m, где n-m – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->A|B, A->B|C|baA|e, B->S|bCa|e, C->A|bSa|e}.

3. Определить, принадлежит ли строка a=aabb языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Ab, A->Aa|ba}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q}	{p,q}
q	{s}	{s}
*r	Æ	{r}
s	{r}	{r}

7. Для данного РВ построить ДКА

1^*0^*(0+1)1^*

8.Для данного ДКА исключить состояния r, s  и построить РВ.

	0	1
->p	s	p
*q	p	s
r	r	q
s	q	r

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/1	4/0	2/1	3/0
1	3/0	3/1	1/0	2/1
2	1/1	2/0	3/1	4/0

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать J-K -триггер.

Вариант № 17

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид (ab)ⁿ(ba)ⁿ, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AS|B, A->bSa|bBa|e, B->bCa|e, C->bCa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку bb и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p,q}	{q}
q	{s}	{s}
*r	{r}	Æ
s	{r}	{r}

7. Для данного РВ построить ДКА: 00(0+1)^*+11

8.Для данного ДКА исключить состояния q, s  и построить РВ.

	0	1
->p	s	p
q	p	s
*r	r	q
s	q	r

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/1	1/1	2/1	1/1
1	3/0	3/0	4/1	3/1
2	1/1	2/1	1/0	2/0

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать T-триггер.

Вариант № 18

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n+m – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->С|ASB, A->С|bCa|bSa|e, B->S|bCa|e, C->A|bSa|e}.

3. Определить, принадлежит ли строка a=baab языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0A1|01, 0A->00A1, A->01}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,s}	{q}
*q	{r}	{q,r}
*r	{s}	{p}
s	Æ	{p}

7. Для данного РВ построить ДКА

01^*+0^*1

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q2	q3
*q2	q1	q3
q3	q2	q1

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/0	4/0	2/0	3/0
1	3/0	3/1	1/0	2/1
2	1/1	2/1	3/1	4/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать D-триггер.

Вариант № 19

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид (ab)ⁿ(bb)ⁿ, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка. R={S->AA|BB, A->bCa|bBa|e, B->bBa|e, C->bSa|e}.
3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->AB, AB->BA, A->a, B->b}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,r}	{q}
q	{s}	{s,r}
*r	{r}	{p}
s	Æ	{p}

7.Для данного РВ построить ДКА

(00+11)^*

8.Для данного ДКА исключить состояние q₃  и построить РВ.

	0	1
-> q1	q2	q1
*q2	q3	q1
q3	q3	q2

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	2/1	4/1
1	3/0	3/1	1/1	3/0
2	4/1	2/1	3/1	1/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать R-S -триггер.

Вариант № 20

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид (ab)ⁿ(bb)^m, где n, m – четные.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка. R={S->A|B|ASB, A->bCa|bSa|e, B->bCa|e, C->bSa|e}.
3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->A|B, A->aAb|0, B->aBbb|1}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p}	{q}
*q	{s}	{s,r}
*r	{r,s}	{q,r}
s	Æ	{q}

7. Для данного РВ построить ДКА

1^*00^*(1+0)

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q3	q1
*q2	q2	q1
q3	q2	q3

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	4/1	4/1
1	3/1	3/0	2/0	1/1
2	4/1	1/1	1/1	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать J-K -триггер.

Вариант № 21

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿ⁺²b^n-2, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AC|BA, A->baB|bAa|e, B->bSa|e, C->bBa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0A|1S, A->0A|1B, B->0B|1B|1}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,p}	{p}
q	{r,s}	{t}
r	{p,r}	{t}
*s	Æ	Æ
*t	Æ	Æ

7. Для данного РВ построить ДКА

1^*(0+1)^*0^*

8.Для данного ДКА исключить состояние q₂  и построить РВ.

	0	1
-> q1	q2	q3
q2	q1	q3
*q3	q2	q1

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	1/0	4/1	1/0
1	4/0	2/1	2/0	4/1
2	2/0	4/1	3/0	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать T-триггер.

Вариант № 22

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n-m – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->С|A|B, A->S|bCa|e, B->S|bCa|e, C->B|bSa|e}.

3. Определить, принадлежит ли строка a=baab языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0S|S0|D, D->DD|1A|e, A->0B|e, B->0A|0}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{r,s}	{q}
*q	{p}	{q,p}
r	{s}	{p}
*s	{p}	Æ

7. Для данного РВ построить ДКА

0^*(0+1) 1^*

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q3	q2
*q2	q3	q1
q3	q1	q2

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	3/0	4/0	2/1	2/1
1	4/1	1/1	3/1	4/1
2	2/0	4/0	4/1	3/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать D-триггер.

Вариант № 23

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿ⁺²b^n-2, где n – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AC|BA, A->baB|bAa|e, B->bSa|e, C->bBa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ab и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0A|1S|e, A->1A|0B, B->0S|1B}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q}	{q,s}
*q	{q,r}	{r}
*r	{p}	{s}
s	{p}	Æ

7. Для данного РВ построить ДКА

00(00)^*+11(11)^*

8. Для данного ДКА исключить состояние q₂ и построить РВ.

	0	1
-> q1	q1	q2
q2	q2	q3
*q3	q3	q3

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/0	1/0	2/1	1/1
1	3/0	3/0	4/0	3/0
2	1/1	2/1	1/1	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать R-S -триггер.

Вариант № 24

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb²aⁿ, где n – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без леворекурсивных правил.

R={S->BaA|SbB, A->Abb|aCa|e, B->bBa|e, C->bCa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку aa и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->SS|A, A->a|bb}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q}	{p,q}
q	{s}	{s}
*r	Æ	{r}
s	{r}	{r}

7.Для данного РВ построить ДКА

1^*0^*(0+1)1^*

8.Для данного ДКА исключить состояния r, s  и построить РВ.

	0	1
->p	s	p
*q	p	s
r	r	q
s	q	r

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/1	4/0	2/1	3/0
1	3/0	3/1	1/0	2/1
2	1/1	2/0	3/1	4/0

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать J-K -триггер.

Вариант № 25

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n+m – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без цепных продукций, где e  – пустая строка:

R={S->A|B|ASB, A->B|bCa|bSa|e, B->C|bCa|e, C->A|bSa|e}.

3. Определить, принадлежит ли строка a=abba языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Aba|e, B->bSA, AA->c}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p,q}	{q}
q	{s}	{s}
*r	{r}	Æ
s	{r}	{r}

7.Для данного РВ построить ДКА: 00(0+1)^*+11

8.Для данного ДКА исключить состояния q, s  и построить РВ.

	0	1
->p	s	p
q	p	s
*r	r	q
s	q	r

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/1	1/1	2/1	1/1
1	3/0	3/0	4/1	3/1
2	1/1	2/1	1/0	2/0

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать T-триггер.

Вариант № 26

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n-m – четное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C,D}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->AB|CD, A->aAb|C|e, B->bBa|C|e, C->abSba|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку ba и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->a|Ba, B->Bb|b}
6. Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,s}	{q}
*q	{r}	{q,r}
*r	{s}	{p}
s	Æ	{p}

7. Для данного РВ построить ДКА

01^*+0^*1

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q2	q3
*q2	q1	q3
q3	q2	q1

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	2/0	4/0	2/0	3/0
1	3/0	3/1	1/0	2/1
2	1/1	2/1	3/1	4/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать D-триггер.

Вариант № 27

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb^m, где n-m – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->A|AS, A->abA|Ba|e, B->Bba|bC|e, C->bCa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку aa и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->Ab, A->Aa|ba}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{q,r}	{q}
q	{s}	{s,r}
*r	{r}	{p}
s	Æ	{p}

7.Для данного РВ построить ДКА

(00+11)^*

8.Для данного ДКА исключить состояние q₃  и построить РВ.

	0	1
-> q1	q2	q1
*q2	q3	q1
q3	q3	q2

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	2/1	4/1
1	3/0	3/1	1/1	3/0
2	4/1	2/1	3/1	1/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать R-S -триггер.

Вариант № 28

1. Построить грамматику G, которая порождает язык L(G) в алфавите V={a,b} все строки которого имеют вид aⁿb²aⁿ, где n – нечетное число.
2. Задана формальная грамматика G=<{a,b},{S, A, B, C}, R,S>. Построить эквивалентную ей формальную грамматику G’ без продукций вида a->e, где e  – пустая строка.

R={S->BaA|SbB, A->Abb|aCa|e, B->bBa|e, C->bCa|e}.

3. Получить множество строк, не более 4 знаков, содержащих подстроку aa и принадлежащих языку L, порожденному грамматикой G из задачи 2.
4. Является ли язык L, порождаемый грамматикой G из задачи 2 бесконечным?
5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? R={S->0A1|01, 0A->00A1, A->01}

6.Дан НКА. Найти эквивалентный ему ДКА

	0	1
->p	{p}	{q}
*q	{s}	{s,r}
*r	{r,s}	{q,r}
s	Æ	{q}

7. Для данного РВ построить ДКА

1^*00^*(1+0)

8. Для данного ДКА исключить состояние q₃ и построить РВ.

	0	1
-> q1	q3	q1
*q2	q2	q1
q3	q2	q3

9. Минимизировать конечный автомат Мили A, заданный таблицей и построить неотличимый от него минимальный автомат Мура Am.

A\Q	1	2	3	4
0	1/1	4/1	4/1	4/1
1	3/1	3/0	2/0	1/1
2	4/1	1/1	1/1	2/1

10. Синтезировать структурную схему для заданного в п. 1 автомата Мили, в качестве элементарного автомата использовать J-K -триггер.

Список вопросов к экзамену по дисциплине  «Теория автоматов»

1. Предмет дисциплины «Теория автоматов» (ТА). Прикладной аспект ТА. Методы доказательств, используемые в ТА.
2. Формальные грамматики и языки: основные понятия и определения. Операции над языками.
3. Типы формальных грамматик. Деревья вывода. Неоднозначные грамматики.
4. КС-грамматики. Удаление бесполезных и недостижимых символов КС-грамматик.
5. КС-грамматики. Удаление леворекурсивных правил. Исключение цепных правил.
6. КС-грамматики. Удаление пустых правил.
7. Теорема о разрешимости проблемы пустоты КС-языков.
8. Теорема о разрешимости проблемы бесконечности КС-языков.
9. Неразрешимые проблемы грамматик.
10. Магазинные автоматы.
11. Формальное определение магазинного автомата.
12. Теорема о КС-грамматике и магазинном автомате.
13. Теорема о магазинном автомате и КС-грамматике.
14. Языки магазинного автомата.
15. Детерминированный магазинный автомат.
16. Недетерминированный магазинный автомат.
17. Двустековый магазинный автомат.
18. Конечные автоматы. ДКА. Способы представления
19. Недетерминированный КА. Язык НКА.
20. Эквивалентность НКА и ДКА
21. КА с e-переходами. e-замыкание. Устранение e-переходов.
22. Регулярные выражения и языки. Построение РВ. КА и РВ.
23. Преобразование ДКА в РВ методом исключения состояний
24. Преобразование РВ в ДКА
25. Свойства замкнутости и разрешимости РЯ
26. Эквивалентность состояний
27. Эквивалентность РЯ. Минимизация конечных автоматов.
28. МТ. Определение. Диаграмма переходов для МТ. Язык МТ. Память МТ.
29. Определение абстрактного автомата. Способы задания абстрактного автомата
30. Синхронные и асинхронные автоматы. Автоматы Мура и Мили
31. Построение автомата Мили по автомату Мура.
32. Построение автомата Мура по автомату Мили.
33. Абстрактный и структурный синтез автомата. Теорема о структурной полноте
34. Полные автоматы. Кодирование алфавитов автомата.
35. Пример канонического синтеза абстрактного автомата.
36. Гонки в автоматах. Противогоночное кодирование состояний абстрактных автоматов
37. Композиция автоматов. Основные виды соединения автоматов.
38. Типы элементов памяти. D и Т триггеры.
39. Типы элементов памяти. R-S-триггер.
40. Типы элементов памяти. J-K-триггер.
41. Типы элементов памяти. R-S-T-триггер.
42. Обобщенная классификация автоматов.

Темы рефератов

1. Приложение конечных автоматов: поиск в тексте
2. Применение регулярных выражений. Регулярные выражения в UNIX. Лексический анализ.Поиск образцов в тексте
3. Деревья разбора. Построение деревьев разбора. Крона дерева разбора. Вывод, порождение и деревья разбора.
4. Приложения контекстно-свободных грамматик. Синтаксические анализаторы. Генератор синтаксических анализаторов YACC
5. Приложения контекстно-свободных грамматик. Языки описания документов. XML и определения типа документа
6. Расширения базовой машины Тьюринга. Многоленточные машины Тьюринга. Эквивалентность одноленточных и многоленточных машин Тьюринга
7. Машины Тьюринга с ограничениями. Машины Тьюринга с односторонними лентами
8. Машины Тьюринга с ограничениями. Мультистековые машины
9. Машины Тьюринга с ограничениями. Счетчиковые машины. Мощность счетчиковых машин
10. Машины Тьюринга и компьютеры. Имитация машины Тьюринга на компьютере
11. Машины Тьюринга и компьютеры. Имитация компьютера на машине Тьюринга. Сравнение времени работы компьютеров и машин
12. Деревья вывода в КС-грамматиках
13. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов
14. Трансляторы и трансляции
15. Трансляторы, интерпретаторы и компиляторы. Стадии работы компилятора. Построение компилятора.
16. Способы задания схем грамматик. Форма Наура-Бэкуса.
17. Способы задания схем грамматик. Итерационная форма.
18. Способы задания схем грамматик. Синтаксические диаграммы.
19. Грамматики, описывающие основные конструкции языков программирования. Описание списков.
20. Грамматики, описывающие основные конструкции языков программирования. Грамматики, описывающие целые числа без знака и идентификаторы.
21. Грамматики, описывающие основные конструкции языков программирования. Грамматики для арифметических выражений.
22. Грамматики, описывающие основные конструкции языков программирования. Грамматика для описаний.
23. Грамматики, описывающие основные конструкции языков программирования. Грамматика, задающая последовательность операторов присваивания.
24. Грамматики, описывающие основные конструкции языков программирования. Грамматики, описывающие условные операторы и операторы цикла
25. Рекомендации по построению грамматик. Пример построения грамматик.
26. КС-грамматики. Нормальная форма Хомского
27. КС-грамматики. Нормальная форма Грейбах

Литература

1 Основная литература

1. Выхованец В.С. Теория автоматов: Учеб. пособие для вузов. — Тирасполь, ПГУ, 2001. – 102 с.
2. Выхованец В.С. Сборник задач по теории автоматов: Учеб. пособие для вузов. — Тирасполь, ПГУ, 2001. – 56 с.
3. ХопкрофтД., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, М.:2002
4. Горбатов В.А. Фундаментальные основы дискретной математики. Учебник. М.: Наука. Физматлит, 2000. – 544 с.
5. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учебное пособие для втузов. – СПб.: Политехника, 1996. – 885 с.
6. Карпов Ю.Г. Теория автоматов. Учебник для вузов. Питер, 2002

 

2 Дополнительная литература

1. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М.: Наука, 1985. – 320 с.
2. Брой М. Информатика. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация: В 4-х ч. Ч. 4. – М.: Диалог-МИФИ, 1998. – 224 с.
3. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. – М.: Радио и связь, 1986. – 272 с.
4. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. – М.: Радио и связь, 1990. – 304 с.
5. Братчиков И.Л. Синтаксис языков программирования. – М.: Наука, 1975. – 232 с.
6. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. – М.: Радио и связь, 1988. – 128 c.
7. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е изд., перераб. и доп. – М.: Энергоатомиздат, 1988. – 480 с.: ил.