Сучкова Л.И. Абстрактный и структурный синтез автоматов
Подождите немного. Документ загружается.
121
Структурный синтез выполняется на базе выбранных
элементов памяти.
8 УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБО-
ТЫ
Приведенные ниже задания предназначены для выпол-
нения лабораторных работ по курсу «Теория автоматов» по
разделам, связанным с синтезом, преобразованиями абст-
рактных и структурных автоматов. Для выполнения заданий
следует предварительно изучить соответствующий теорети-
ческий материал и примеры выполнения
заданий.
8.1 Синтез автоматов-распознавателей
Задание:
1. Построить автомат, распознающий заданный регу-
лярный язык;
2. Построить эквивалентный детерминированный авто-
мат-распознаватель;
3. Построить праволинейную и леволинейную грамма-
тики, порождающие языки, распознаваемые построенным
детерминированным автоматом.
Варианты заданий:
1.
(bac)
+
∪ cb
+
(ba)
+
∪ b
*
ac
*
2. (a
*
dc
+
∪ acd
*
)
*
3. k
*
c
*
d ∪ (kda)
+
b
*
4. (a
+
d
*
c)
*
∪ ab
*
c
5. (ba)
*
ca
+
∪ b
*
a
+
c
*
6. (bc)
*
cc
+
∪ bc
*
∪ ab
*
7. d
+
ac
*
∪ (dbc)
+
ac
*
8. (a
*
ba)
+
∪ a
+
(bc)
+
9. b (kab)
+
d
+
∪ (b
*
c)
*
10. (k
*
a)
+
b ∪ ka
+
d
*
11. cac
+
(ba)
*
∪ (ca)
*
cb
*
122
12. (ab
*
c
+
∪ с
+
da
*
)
*
13. c (daa)
*
(ca)
*
∪ ca
*
ac
*
14. (ba)
+
c
*
a ∪ (bca)
*
∪ (ba)
*
c
15. cc (ba)
+
∪ (ca)
+
a
*
∪ c
*
(ba)
*
16. (ca)
+
∪ (bc)
*
∪ (cc
*
a ∪ ca)
*
17. (ca
+
b)
+
∪ (ba)
*
∪ bc
*
(ab)
*
18. (b
+
cd
+
)
*
∪ b
*
cdc
*
19. bac
*
∪ (bca)
+
(ba)
*
20. Дополнение b
*
a ∪ ba b
+
21. Дополнение bac
*
∪ (bca)
+
22. (c*ab)
+
∪ (ba)
+
∪ b*c*
23. (kc)
*
c d* ∪ (dc)
+
b*
24. (a
+
d∪ cd*)
*
∪ ab
*
c
25.
(ca
+
b)
*
∪ (ba)
+
∪ bc
*
8.2 Построение МП-автомата
Задание: для заданного языка построить распознающий
его МП-автомат. Продемонстрировать использование правил
автомата для разбора заданной цепочки
α, приведя изменение
его конфигураций по тактам работы автомата.
Варианты заданий:
1. L = ba
*
∪ c (ba)
+
a
k
cb
k
k ≥ 0 α = cbabaacb
2. L = ((a
*
b
+
(cd)
n
a
n
)
*
∪ df
*
c
+
)
+
n ≥ 0 α = dffccaabcdcdaa
3. L = (a
+
b)
n
k
*
(bc)
n
a
*
n ≥ 1 α = aabaabkbcbc
4. L = (b
+
c
*
)
n+1
a
*
(f
*
d ∪ a
+
)
n
n ≥ 0 α = bbccbbaaaaa
5. L = (a
n
c
*
b
2n + 1
∪ a
m + k + 1
b
2k + 2
∪ bc
*
a (bc)
+
)
*
n, m, k ≥ 0 α = aacbbbbbbabc
123
6. L = (a
*
bc
+
∪ (bc)
*
a
n+m
b
m
с
2n
)
+
n, m ≥ 0 α = bcaabccaabccc
7. L = (a
n
b
n+2
)
+
bca
*
n ≥ 0 α = abbbbcaaa
8. L = (a
*
b
k
r a
k
c
+
)
*
k ≥ 1 α = bbraccc
9. L = (ab)
+
∪ (ca)
n+k
(bc
+
∪ b
*
ca
+
)
2n
∪ a
*
n, k ≥ 0 α = cacacabbbcaadcccc
10. L = a
k
a
*
bc
+
b
k+3
(c
+
∪ a
*
b) t
k ≥ 0 α = aaabccbbbct
11. L = (a
n
bc
n
∪ a
+
b)
+
n ≥ 0 α = aaabccc
12. L = (bc
+
)
n
c
+
ab
*
a
n
n ≥ 0 α = bcccaa
13. L = a
n+1
c
k
m
+
d
k
t
*
b
n
k, n ≥ 0 α = aaccmmmddb
14. L = a
*
b
n
a
*
b
2m
(cb)
m
(ab
*
c ∪ bca
*
)
2n
n, m ≥ 0 α = aabbbcbabbcbcaa
15. L = ab
*
c (ab)
+
∪ a
*
α = acabab
16. L = a
+
(bc)
+
b ∪ a
n
b
*
c
n
n ≥ 0 α = abcbcbcb
17. L = a
n
b c
n
∪ (abc)
*
n ≥ 0 α = abcabc
18. L = (bc)
n+2
a
+
(ab)
2n
n ≥ 0 a = bcbcaaa
19. L = bca
*
∪ (ab
*
c
2n
b
*
(ab ∪ bca
*
)
n+k
)
+
n, k ≥ 1 a = abccbbbabbcaaa
20. L = a
n
(bca
m
b
2m+3
∪ a
*
) b
n
n, m ≥ 0 a = aabcabbbbbbb
21. L = c
+
a
n
(ba
*
∪ a
m
b
m
) (ba)
n
n ≥ 1; m ≥ 0 a = ccabba
124
22. L = ab
*
∪ a
k
a
n
tc
n
b
k+2
n ≥ 0; k ≥ 0 a = aatbbbb
23. L = (b
*
a)
n
b
+
a
n
∪ c
+
a
m
b
2m
n ≥ 0, m ≥ 1 a = bbbabba
24. L = bca
+
∪ b
k
b
*
a
k
k ≥ 0 a = bbbbaaa
8.3 Построение машины Тьюринга
Задание:
1. Определить, какую функцию вычисляет заданная
машина Тьюринга, и записать ее аналитический вид.
2. Построить машину Тьюринга, вычисляющую за-
данную функцию.
Варианты заданий:
№1
1) f(x, y, z) = ?
ε →
1
L
1
→
ε
R
1
→
1
R
ε
→
ε
R
1
→
ε
R
∗
→
1
R
∗ →
∗
R
2)
⎩
⎨
⎧
≥+++
<+−+
=
.5,27
,5,3
),,(
yxyx
yxyx
zyxf
№2
1) f(x, y, z) = ?
125
1
→
1R
1 → 1R
ε
→
1E
∗
→
1R
∗ →
1R
∗
→
∗
E
1
→
1R
2)
⎪
⎩
⎪
⎨
⎧
=
≤<−−
>++
=
.0,1
,30,1
,3,2
),(
y
yyx
yyx
yxf
№3
1) f(x) = ?
1 →
1
R
1 → ε
R
ε →
1
L
ε
→
1
E
ε
→
1
R
2)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
≥++
<
−
+
=
.2,
3,
2,
),,,(
xy
xtzy
x
tx
zy
tzyxf
№4
1) f(x, y, z) = ?
126
1 → 1
R
∗ → 1
R
ε →
1
L
1
→
1
E
ε
→
1
E
1
→
1
L
ε
→
1
L
1
→
1
L
2)
⎪
⎩
⎪
⎨
⎧
>+
≤+
=
.2,
,2,
),,(
zyx
zy
y
x
zyxf
№5
1) f(x, y, z) = ?
1 → ε
R
ε → ε
L
1
→
ε
R
1
→
ε
R
∗ →
ε
L
∗ → 1
L
ε
→
ε
L
ε
→
ε
E
∗
→
ε
R
2)
⎪
⎩
⎪
⎨
⎧
>>++
≤>
−
≤
=
.3&1,
,3&1,
2
,1,0
),,(
zxzyx
zx
z
x
x
zyxf
№6
1) f(x, y, z) = ?
127
1 → 1
R
∗ →
1
R
ε
→
ε
E
1
→
1
R
∗
→
1
R
1
→
1
E
2)
⎪
⎩
⎪
⎨
⎧
=
<−
≥−
=
.2,1
,2,1
,3,2
),,(
x
xxy
xy
zyxf
№7
1) f(x, y, z) = ?
ε
→
ε
E
∗
→
ε
R
∗ → ε
R
1
→
ε
R
1 → ε
R
1
→
1
R
∗
→
1
R
2)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
<
−
≤≤+
>+
=
.3,
2
,43,
,4,1
),(
y
y
x
yyx
yx
yxf
№8
1) f(x, y, z, t) = ?
128
1
→
1
R
1 → 1
R
ε
→
ε
E
∗ →
1
R
∗
→
1
R
2)
⎪
⎩
⎪
⎨
⎧
>−++
≤
−
++
=
.3,2
,3,
2
1
),,(
zzyx
z
z
yx
zyxf
№9
1) f(x) = ?
1 → ε
R
1
→
ε
R
ε → 1
L
ε
→
1
L
ε
→
1
L
2)
⎩
⎨
⎧
>−+
≤++
=
.1,
,1,1
),,(
yzyx
yyx
zyxf
№10
1) f(x, y) = ?
1 → ε
R
∗ → ε
R
ε →
1
L
ε
→
1
L
129
2)
⎩
⎨
⎧
≤−−
>++
=
.2,1
,2,12
),,(
yyx
yyx
zyxf
№11
1) f(x, y, z) = ?
1 → ε
R
1
→
ε
R
1
→
1
R
∗ → ∗Ε
ε
→
1
E
∗
→
1
R
∗ →
∗Ε
2)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
>>
≤>
−
≤
=
.3&1,
,3&1,
2
,1,1
),(
yxy
yx
y
x
x
yxf
№12
1) f(x, y) = ?
1 → ε
R
∗ → ∗Ε
1
→
1
E
∗
→
1Ε
130
2)
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
>>++
≤>
+
≤
−
+
=
.3&3,
,3&3,
,3,
1
),,(
yzzyx
yz
y
yx
z
z
yx
zyxf
№13
1) f(x, y, z, t) = ?
1 → 1Ε
1
→
1
R
1
→
ε
R
∗
→
1
R
∗ →
∗
E
ε
→
ε
L
∗ → ε
R
2)
⎪
⎩
⎪
⎨
⎧
++
≤≤
>>÷
=
иначеyx
yxyx
yxyx
zyxf
.,2
,2&2,
,2&2,
),,(
№14
1) f(x, y) = ?
1 → 1
R
∗ → 1
R
ε →
1
L
1
→
1
E
ε
→
1
R
1
→
1
L
ε
→
1
L
1
→
1
L