-
Notifications
You must be signed in to change notification settings - Fork 2
/
app-coursew-variants.tex
113 lines (104 loc) · 12.7 KB
/
app-coursew-variants.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
\renewcommand{\theAlgoEnv}{\Alph{chapter}.\arabic{AlgoEnv}}
\chapter{Варианты заданий}
Задание 1
\begin{enumerate}
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых единицы встречаются только четное число раз, а первая сдвоенная пара нулей может появиться только после появления двух единиц.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых единицы встречаются только нечетное число раз, а после последней сдвоенной пары нулей может появиться не более трех единиц.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых после второй сдвоенной пары нулей количество единиц четно.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых до второй сдвоенной пары нулей количество единиц четно.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых, если в слове содержится три последовательные буквы, то оно содержит хотя бы два нуля.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых число единиц делится на 2, а число нулей -- на 3.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, которые начинаются или оканчиваются (или и то и другое) последовательностью 01.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых хотя бы на одной из последних трёх позиций стоит 1, и не встречается более двух нулей подряд.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий либо из повторяющихся один или несколько раз фрагментов 01, либо повторяющихся один или несколько раз фрагментов 010, либо всех слов четной длины и содержащих хотя бы одно подслово 00.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых если встречается три подряд идущих нуля, то слово имеет чётную длину, а если встречается две подряд идущие единицы, то длина слова нечётная.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых если встречается хотя бы одна пара 01, то пара 10 должна встретиться не менее двух раз.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых если слово содержит пару 10, то оно имеет четную длину и должно обязательно заканчиваться двумя подряд идущими единицами.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых не встречаются подслова 101 и 110 одновременно.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых четное число единиц может быть тогда и только тогда, когда слово содержит послово 101.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, которые имеют четную длину тогда и только тогда, когда они содержат подслово 011.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых количество единиц четно, а пара сдвоенных нулей встречается не более трех раз.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, содержащих не более трёх подряд идущих нулей, и количество единиц в которых четно.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых после третьей слева единицы стоит четное число групп вида $01$.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых количество нулей четно, а первая сдвоенная пара единиц появляется не раньше группы строенных нулей.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, содержащих нечетное количество нулей и единиц, начинаться и заканчиваться слова могут не более чем тремя подряд идущими нулями.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, не содержащих двух смежных нулей, и в которых группа цифр $010$ повторяется не более одного раза.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, содержащих три смежные единицы, и в которых группа вида $101$ содержится не более одного раза.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых между двумя парами единиц может находиться не более чем три подряд идущих нуля.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых после группы $010$ следует чётное количество подряд идущих единиц.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых перед тремя подряд идущими нулями находится четное количество единиц.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, таких что если слово начинается с нуля, то количество единиц в слове четно, а если с единицы, то нечетно.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых если встречается хотя бы одна группа из трех подряд идущих нулей, то пара сдвоенных единиц должна появиться не менее двух раз.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых если слово содержит группу цифр 010, то оно имеет нечетную длину.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, в которых группа строенных нулей и строенных единиц не встречаются одновременно.
\item Язык над алфавитом $\Sigma=\{0,1\}$, состоящий из всех слов, имеющих четную длину тогда и только тогда, когда они начинаются тремя нулями, а заканчиваются тремя единицами.
\end{enumerate}
\bigskip
Задание 2
\begin{enumerate}
\item $\Sigma = \{0,1,2\}$, $A = \{01110, 1011, 11100, 010101\}$.
\item $\Sigma = \{0,1,2\}$, $A = \{110, 1110, 0000, 0111\}$.
\item $\Sigma = \{0,1,2\}$, $A = \{1011, 111, 0110, 10011\}$.
\item $\Sigma = \{a,b,c\}$, $A = \{bbab, ccac, bacb, baabc\}$.
\item $\Sigma = \{a,b,f\}$, $A = \{faafb, ffba, bfab, affa\}$.
\item $\Sigma = \{1,2,3\}$, $A = \{2112, 1233, 1322, 131313\}$.
\item $\Sigma = \{4,5,6\}$, $A = \{5555, 4665, 666, 4455, 665\}$.
\item $\Sigma = \{9,10,11,12\}$, $A = \{9101112, 101111, 121110, 121211\}$.
\item $\Sigma = \{0,1,2,3,4,5\}$, $A = \{22231, 1213, 0001, 11101\}$.
\item $\Sigma = \{0,1,2,3,4,5\}$, $A = \{000, 010, 221, 3334, 0110\}$.
\item $\Sigma = \{a,b,c,d,e\}$, $A = \{aaac, bbd, bbe, abbc\}$.
\item $\Sigma = \{a,b,c,d,e\}$, $A = \{aaaa, bbbba, bbaa, cccac\}$.
\item $\Sigma = \{x,y,v,w,z\}$, $A = \{xyz, xyzz, zzzw, xyyw\}$.
\item $\Sigma = \{0,1,2,3,4,5\}$, $A = \{01112, 32544, 12124, 5551\}$.
\item $\Sigma = \{a,b,w,z\}$, $A = \{wwwz, bbbww,zzbz,wzwzw\}$.
\item $\Sigma = \{0, 1, 2\}$, $A = \{010100, 111001, 110, 1110\}$.
\item $\Sigma = \{0, 1, 2\}$, $A = \{001100, 111, 0101, 1000\}$.
\item $\Sigma = \{0, 1, 2\}$, $A = \{1011, 0000, 1111, 1011101\}$.
\item $\Sigma = \{0, 1, 2\}$, $A = \{011100, 11101, 1010, 111\}$.
\item $\Sigma = \{x, y, z\}$, $A = \{xxyy, xxxy, xyxyyy, xyxyyx\}$.
\item $\Sigma = \{x, y, z\}$, $A = \{xy, yxxy, yxyxxy, xyxxx\}$.
\item $\Sigma = \{x, y, z\}$, $A = \{xyx, xxy, yyyxxy, xyxyx\}$.
\item $\Sigma = \{3, 5, 0\}$, $A = \{03530, 0033, 30335, 0350\}$.
\item $\Sigma = \{9, 8, 7\}$, $A = \{987, 99787, 87799, 9777\}$.
\item $\Sigma = \{3, 5, 0\}$, $A = \{3330, 05033, 30330, 535\}$.
\item $\Sigma = \{x, a, 35\}$, $A = \{35aaxx, xx35ax, 35xa, 3535ax\}$.
\item $\Sigma = \{10, 23, 45, 96\}$, $A = \{101045, 45109623, 23102345, 1010\}$.
\item $\Sigma = \{0, 1, 2, 3, 4, 5\}$, $A = \{0112, 0033, 30121, 331\}$.
\item $\Sigma = \{0, 1, 2, 3, 4, 5\}$, $A = \{53150, 53555, 5510, 0001\}$.
\item $\Sigma = \{a, b, c, d, e\}$, $A = \{abaac, ccbac, ccc, abac\}$.
\end{enumerate}
\bigskip
Задание 3
\begin{enumerate}
\item $L_1 = (10+1)^\ast11(0+1)^\ast$, $L_2 = (101)^\ast111(0+1)^\ast$.
\item $L_1 = (0+1)^\ast1^\ast01(11+0)^\ast$, $L_2 = 1^\ast(0+1+11)^\ast0$.
\item $L_1 = 11(01+10)^\ast001^\ast$, $L_2 = 11((10)^\ast(01)^\ast)^\ast0011^\ast$.
\item $L_1 = (00+11)^\ast10(10+01)^\ast$, $L_2 = (0+1)^\ast1$.
\item $L_1 = (1+01)^\ast(00+1)^\ast$, $L_2 = (0+10)^\ast(11+0)^\ast$.
\item $L_1 = (111+01)^\ast1(00+11)^\ast$, $L_2 = 1^\ast0^\ast$.
\item $L_1 = (01+11)^\ast(10+11)^\ast$, $L_2 = (10+11)^\ast(01+11)^\ast$.
\item $L_1 = (a+bb)^\ast bba^\ast$, $L_2 = a^\ast (bb)^\ast a^\ast$.
\item $L_1 = b^\ast ab(ab+a)^\ast$, $L_2 = b^\ast a^\ast ab$.
\item $L_1 = a^\ast b^\ast(a+b)(bb)^\ast$, $L_2 = a^\ast(aa+b)^\ast$.
\item $L_1 = (b+ab)^\ast(a+ab)b^\ast$, $L_2 = (ab)^\ast b^\ast$.
\item $L_1 = (aba+bab)^\ast$, $L_2 = (ab + ba)^\ast$.
\item $L_1 = b(a+ba)^\ast (ab)^\ast$, $L_2 = b(a+ba+ab)^\ast$.
\item $L_1 = (aa+bb)^\ast ba(a+b)^\ast$, $L_2 = (aa)^\ast(bb)^\ast a^\ast b^\ast$.
\item $L_1 = ((a+b)^\ast + (ab+ba)^\ast)^\ast$, $L_2 = (a+b+ab+ba)^\ast$.
\item $L_1 = (1+01)^\ast010(10+01)^\ast$, $L_2 = (10)^\ast(0+10)10(1+0)^\ast$.
\item $L_1 = (0+1)^\ast010^\ast1(111+01)^\ast$, $L_2 = 0^\ast(10+11)^\ast0^\ast(1+0)^\ast$.
\item $L_1 = 01(0+1+10)^\ast01^\ast0$, $L_2 = 011((11)^\ast(10)^\ast)^\ast1^\ast001^\ast$.
\item $L_1 = (00+11)^\ast01(101+01)^\ast$, $L_2 = (0+1)^\ast1^\ast(0+1)^\ast0^\ast10^\ast$.
\item $L_1 = (11+00)^\ast(101+0)^\ast$, $L_2 = (11+000)^\ast(1+01)^\ast$.
\item $L_1 = (101+111)^\ast0(01+10)^\ast1$, $L_2 = 1^\ast0^\ast$.
\item $L_1 = (1+011)^\ast(01+11)^\ast$, $L_2 = (11+00)^\ast(01+10)^\ast$.
\item $L_1 = (aa+bbb)^\ast b^\ast ab^\ast$, $L_2 = a^\ast (bab)^\ast b^\ast$.
\item $L_1 = b^\ast bba^\ast (ab+b)^\ast$, $L_2 = a^\ast ba^\ast ab$.
\item $L_1 = a^\ast b^\ast (a+b+ab+ba)ab^\ast$, $L_2 = a^\ast (bb+aa)^\ast$.
\item $L_1 = (a+ab)^\ast b^\ast (b+ba)a^\ast$, $L_2 = (a+b)b^\ast (ab+bb)^\ast$.
\item $L_1 = (aba+b)^\ast (ab+a)^\ast$, $L_2 = (abb+baa)^\ast$.
\item $L_1 = b(a+b)^\ast (bb+aab)^\ast$, $L_2 = a(a+ab)(b+ab)^\ast$.
\item $L_1 = (aa+bb)^\ast a^\ast ab (a+ba)^\ast$, $L_2 = (aa)^\ast a(a+b)^\ast (bb)^\ast$.
\item $L_1 = (ab)^\ast (a+b)(b+a)(a+bab)^\ast$, $L_2 = ((a+b)^\ast + (aa+bb)^\ast)^\ast$.
\end{enumerate}
\end{itemize}