Wykonanie: Krakowian Konrad 140059 Rakowski Bartosz 140116

mgr inż. A. Sterna Poniedziałek, godz. 15.15 08.05.2006r.

Sprawozdanie nr 9

KOMPUTEROWA SYNTEZA AUTOMATU Z PARAMETREM WEWNETRZNYM

1. Cel ćwiczenia

Celem ćwiczenia jest praktyczne zapoznanie się ze sposobem komputerowej syntezy automatów z parametrem wewnętrznym.

2. Program ćwiczenia:

1. Określenie grafów G <A> i wyrażenia symbolicznego G_i⁺:

	y2	y3	y1	y1	y3	y2	y3	y1	y2
	q1	q2	q3	q4	q5	q6	q7	q8	q9
z1	q2	q4	q9	q2	q9	q7	q4	q9	q6
z2	q5	q7	q7	q1	q8	q3	q7	q9	q3

y₂ y₂

z₁,z₂ z₁ z₁

z₂

y₁ z₁ z₁ y₃

z₂ z₂

z₁ z₂ z₂

z₁

z₂ y₃

z₁ y₁

z₁ z₁

z₂

y₂

y₃ y₁

G_i⁺ = ⁰(q₁¹(z₁q₁²(z₁q₄³(z₁q₂,z₂q₁)³,z₂q₇³(z₁q₄,z₂q₇)³)²,z₂q₅²(z₁q₉³(

z₂q₃⁴(z₁q₉,z₂q₇)⁴,z₁q₆⁴(z₂q₃,z₁q₇)⁴)³,z₂q₈³(z₁q₉,z₂q₉)³)²)¹)⁰

2. Wyniki syntezy automatu uzyskane w programie „apw.exe”:

Po przeanalizowaniu grafu, okazało się, że jest tylko jedna możliwość podziału danego automatu na trzy podgrafy:

q₁,q₂,q₄*q₃,q₇,q₆*q₅,q₈,q₉

Wyniki syntezy automatu z parametrem wewnętrznym:

1. Określenie zbiorów Qi:

y1 --- {q3,q4,q8} --- b1

y2 --- {q1,q6,q9} --- b2

y3 --- {q2,q5,q7} --- b3

2. Podział grafu na podgrafy:

Podgraf nr 1:

(q1(z2q5,z1q2(z2q7,z1q4(z1q2,z2q1))))

(b2(z2e1b3,z1e1b3(z2e1b3,z1e1b1(z1e1b3,z2e1b2))))

Podgraf nr 2:

(q3(z1q9,z2q7(z1q4,z2q7)),q6(z2q3,z1q7))

(b1(z1e2b2,z2e2b3(z1e2b1,z2e2b3)),b2(z2e2b1,z1e2b3))

Podgraf nr 3:

(q5(z1q9,z2q8(z2q9,z1q9(z1q6,z2q3))))

(b3(z1e3b2,z2e3b1(z2e3b2,z1e3b2(z1e3b2,z2e3b1))))

3. Określenie wyrażenia symbolicznego automatu stanowego <B>:

(b1(z2e2b3,z1e1b3,z2e1b2,z1e3b2,z2e3b2,z1e2b2(z1e1b3,z2e2b1,z1e2b3,z1e3b2,z2e3b1,z2e1b3(z2e1b3,z1e1b1,z2e3b1,z1e3b2,z1e2b1,z2e2b3))))

4. Określenie wyrażenia symbolicznego automatu stanowego <E>:

(e1(b2z2e3,b3z2e2(b3z1e1,b1z1e3(b2z1e2,b2z2e2))))

Graf wyrażenia <B>:

z₁e₁, z₂e₂ z₁e₂ z₂e₂ z₂e₁, z₁e₃, z₂e₃, z₁e₂

z₁e₁ z₂e₃

z₂e₃

z₁e₃

z₂e₁, z₂e₂ z₁e₁, z₁e₂, z₂e₁ z₁e₃

Graf wyrażenia <E>:

b₂z₂ b₃z₂

b₃z₁

b₂z₁, b₂z₂

b₁z₁

1. Określenie struktury logicznej:

W celu określenia struktury logicznej automatu przekształcamy odpowiednio wyrażenia <B> i <E>:

Przejścia ze stanu b1 wyrażenia <B>:

G'** = ⁰(b1¹({[[b1z2]e2],[[b1z1]e1]}b3,{[[b1z2]e1],[[b1z1]e3],

[[b1z2]e3],[[b1z1]e2]}b2²(…))

Przejścia ze stanu b2 wyrażenia <B>:

G'** = ...b2²({[[b2z2]e2],[[b2z2]e3]}b1,{[[b2z1]e3]}b2,{[[b2z1]e1],

[[b2z1]e2],[[b2z2]e1]}b3³(…))

Przejścia ze stanu b3 wyrażenia <B>:

G'** = ...b3³({[[b3z1]e1],[[b3z2]e3],[[b3z1]e2]}b1,{[[b3z1]e3]}b2,

{[[b3z2]e1],[[b3z2]e2]}b3)³)²)¹)⁰

Przekształcone odpowiednio wyrażenie <E>:

G'** = ⁰(e1¹({[[e1b2]z2]}e3,{[[e1b3]z2]}e2²({[[e2b3]z1]}e1,

{[[e2b1]z1]}e3³({[[e3b2]z1],[[e3b2]z2]}e2)³)²)¹)⁰

2. Schematy logiczne:

Schemat logiczny przejść ze stanu b1.

Schemat logiczny przejść ze stanu b2.

Schemat logiczny przejść ze stanu b3.

Schemat logiczny automatu <E>.

3. Uwagi i wnioski:

Dzięki temu ćwiczeniu poznaliśmy sposób komputerowej syntezy automatów z parametrem wewnętrznym przy użyciu laboratoryjnego programu „APW”. Podczas prób podziału grafu na podgrafy, przy zachowaniu wszystkich zasad, zauważyliśmy, ze podgrafy nie mogą zawierać wspólnego wierzchołka. Jest to logiczne, ponieważ wiązałoby się to z przydzieleniem różnych stanów. Po wpisaniu ciągu trzech podgrafów, z których dwa miały wspólny wierzchołek, program automatycznie usuwał powtarzający się wierzchołek z jednego z podgrafów, zachowując przy tym zasadę spójności. W wyniku syntezy otrzymaliśmy wyrażenia <B> i <E>, które następnie przekształciliśmy do odpowiednich form pozwalających na określenie struktury logicznej.

6

e₂

b₃

q₆

q₉

q₈

b₂

e₁

b₁

q₇

q₅

e₃

q₄

q₁

q₃

q₂

---