Курсовая работа5 / Раздел 3
.docКурсовая работа. Раздел 3.
Вариант 19
3.1.2. Построить детерминированный конечный автомат по автоматной грамматике G=<T,N,S,R>. Определить язык допускаемый конечным автоматом.
Терминалы: a, b, c
Нетерминалы: S, A, B, C
Правила:
-
S aA
-
S bS
-
A aA
-
A bB
-
B bS
-
B aC
-
C aC
-
C ε
-
C Bc
Исключим ε-правило
Правила:
-
S aA
-
S bS
-
A aA
-
A bB
-
B bS
-
B aC
-
B a
-
C aC
-
C a
-
C Bc
Построим автомат
Q = {S, A, B, C, E}
Σ = {a, b, c}
Δ = {таблица}
q0 = S
F = {E}
Построим диаграмму
Построим таблицу по диаграмме
|
a |
b |
C |
S |
A |
S |
|
A |
A |
B |
|
B |
C,E |
S |
|
C |
C,E |
|
E |
E |
E |
E |
E |
Построим детерминированный автомат, для этого введем новые состояния.
Обозначим q0 = S; q1 = A; q2 = B; q3 = C,E
Q = {q0, q1, q2, q3}
Σ = {a, b, c}
Δ = {таблица}
q0
F = { q0, q3}
|
a |
b |
C |
q0 |
q1 |
q0 |
|
q1 |
q1 |
q2 |
|
q2 |
q3 |
q0 |
|
q3 |
q3 |
|
q3 |
Автоматом распознается язык, состоящий из следующих цепочек:
b..ba..aba
1..n раз
b..ba..abaa..ac
1..n раз
3.2.8. Определить детерминированный конечный преобразователь, преобразующий множество цепочек, в которых четное количество нулей ограничено произвольным числом единиц, во множество цепочек {1n, где n – число групп с четным количеством нулей}. Цепочки разделяются запятой, последовательность цепочек заканчивается символом «#».
На вход поступают цепочки вида 1n02k1m, 1i02l1j, 1p02v1q…# где n, k, m, I, l, j, p, v, q ≥ 0. Ноль – четное число.
Конечный преобразователь М = < Q, , , , q0, F >:
Σ = { 0, 1, , , #},
= { 1 },
Q = {q0, q1, q2, q3},
Пусть, q0 – начало
q1 – ожидание
q2 – активное
q3 – конец
q0
F = {q3}
|
{ 0 } |
{ 1 } |
{ , } |
{ # } |
||||
q0 |
q2 |
ε |
q1 |
ε |
q0 |
1 |
q3 |
1 |
q1 |
q2 |
ε |
q1 |
ε |
q2 |
1 |
q3 |
1 |
q2 |
q2 |
ε |
q1 |
ε |
q2 |
1 |
q3 |
1 |
q3 |
Ø |
ε |
Ø |
ε |
Ø |
ε |
Ø |
ε |
110011,11100001#
(q0, 110011,11100001#,ε) ˫
(q1, 10011,11100001#,ε) ˫
(q1, 0011,11100001#,ε) ˫
(q2, 011,11100001#,ε) ˫
(q2, 11,11100001#,ε) ˫
(q1, 1,11100001#,ε) ˫
(q1, ,11100001#,ε) ˫
(q2, 11100001#,1) ˫
(q1, 1100001#,1) ˫*
(q2, 0001#,1) ˫*
(q1, #,1) ˫
(q3, ε,11)