Автомат задан набором a,b,q1,q2,q3,q4,q5,Qs,Qf, где a,b – алфавит, Qs – множество начальных состояний (входов),

Автомат задан набором a,b,q1,q2,q3,q4,q5,Qs,Qf, где a,b – алфавит, Qs – множество начальных состояний (входов), Qs – множество конечных состояний (выходов), и списком дуг с метками, определяющими допустимые переходы. Запись i,j,a,b означает, что дуга i,j, идущая из состояния qi в состояние qj, имеет две метки – a и b. Вход Qs=1, выход Qf=4,5, дуги 1,2,a, 1,5,b, 2,4,b, 3,2,a, 4,1,b, 5,4,b, 5,3,b. L0=abmanb|n,m≥0. 1. Построить граф автомата и найти язык L, допустимый автоматом. 2. Детерминизировать автомат. 3. Построить графы автоматов, представляющих языки L0, L∪L0, L°L0 и L*. 4. Из построенных графов удалить -переходы.

1. Построить граф автомата и найти язык L, допустимый автоматом.
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
Определяем язык автомата, решая систему уравнений.
Из начального состояния q1 все состояния достижимы:
x1=ax2+bx5 x2=bx4 x3=ax2 x4=bx1+λ x5=bx3+bx4+λ⇒x1=abx4+bbx3+bbx4+bλx3=abx4 x4=bx1+λ ⇒⇒x1=ab+bbab+bbx4+bλx4=bx1+λ⇒x1=ab+bbab+bbbx1+λ+bλx1=abb+bbabb+bbbx1+ab+bbab+bb+bλ==ab2+b2ab2+b3*ab+b2ab+b2+bλ
Язык допустимый автоматом L=ab2+b2ab2+b3*ab+b2ab+b2+b
2 . Детерминизировать автомат.
1) δq1,a=q2, δq1,b=q5
2) δq2,a=∅, δq2,b=q4
3) δq5,a=∅, δq5,b=q3,q4
4) δq4,a=∅, δq4,b=q1
5) δq3,q4,a=q2∪∅=q2, δq3,q4,b=q1∪∅=q1
{q1}
q2
q3,q4
q4
{q5}
a
a
b
b
b
b
∅ 
a
a
a
a
b
{q1}
q2
q3,q4
q4
{q5}
a
a
b
b
b
b
∅ 
a
a
a
a
b
3. Построить графы автоматов, представляющих языки L0, L∪L0, L°L0 и L*.
L0=abmanb|n,m≥0.
q6
q8
q7
q9
a
b
b
a
b
b
a
q6
q8
q7
q9
a
b
b
a
b
b
a
L∪L0
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
S0
λ
λ 
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
S0
λ
λ 
L°L0
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
λ
λ 
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
λ
λ 
L*
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
t
S0
λ
λ 
λ 
λ 
λ 
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
t
S0
λ
λ 
λ 
λ 
λ 
4

. Детерминизировать автомат.
1) δq1,a=q2, δq1,b=q5
2) δq2,a=∅, δq2,b=q4
3) δq5,a=∅, δq5,b=q3,q4
4) δq4,a=∅, δq4,b=q1
5) δq3,q4,a=q2∪∅=q2, δq3,q4,b=q1∪∅=q1
{q1}
q2
q3,q4
q4
{q5}
a
a
b
b
b
b
∅ 
a
a
a
a
b
{q1}
q2
q3,q4
q4
{q5}
a
a
b
b
b
b
∅ 
a
a
a
a
b
3. Построить графы автоматов, представляющих языки L0, L∪L0, L°L0 и L*.
L0=abmanb|n,m≥0.
q6
q8
q7
q9
a
b
b
a
b
b
a
q6
q8
q7
q9
a
b
b
a
b
b
a
L∪L0
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
S0
λ
λ 
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
S0
λ
λ 
L°L0
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
λ
λ 
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
q6
q8
q7
q9 
a
b
b
a
b
b
a
λ
λ 
L*
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
t
S0
λ
λ 
λ 
λ 
λ 
q1
q2
q3
q4
q5
a
a
b
b
b
b
b
t
S0
λ
λ 
λ 
λ 
λ 
4