26.11.12 Rzeszów

• Politechnika Rzeszowska

• Wydział Elektrotechniki i Informatyki

• Katedra Automatyki i Informatyki

Języki, Automaty i Obliczenia

• PROJEKT (część III)

Algorytm Cocke'a - Youngera - Kasamiego

• Kotowicz Mateusz (127132)

• P07 / 2EF-DI

Wstęp

Wykorzystując algorytm C-Y-K sprawdzić, czy dane słowo należy do generowanego przez podaną gramatykę języka.

Dane

Gramatyka w postaci normalnej Chomsky'ego:

G' = < {S, X, Y, A, B, x, y}, {x, y}, P', S >

S → SB | BX | x

X → AY | AX | x

Y → BY | y

A → x

B → y

Sprawdzane słowo: yxyyy

• Rozwiązanie

Krok 1

j = 1; i = 1..5

V11 = { X|X → y } = {Y, B}

V12 = { X|X → x } = {S, X, A}

V13 = { X|X → y } = {Y, B}

V14 = { X|X → y } = {Y, B}

V15 = { X|X → y } = {Y, B}

Krok 2

j = 2; i=1..4; k=1

dla i = 1:

V12 = {X|X → YZ ; Y ∈ V11, Z ∈ V21} dla k = 1

(-) → YS (-) → YX (-) → YA (-) → BS (-) → BA

S → BX

V12 = {S}

dla i = 2:

V22 = {X|X → YZ ; Y ∈ V21, Z ∈ V31} dla k = 1

(-) → SY (-) → XY (-) → XB (-) → AB

S → SB X → AY

V22 = {S, X}

dla i = 3:

V32 = {X|X → YZ ; Y ∈ V31, Z ∈ V41} dla k = 1

(-) → YY (-) → YB (-) → BB

Y → BY

V32 = {Y}

dla i = 4:

V42 = {X|X → YZ ; Y ∈ V41, Z ∈ V51} dla k = 1

(-) → YY (-) → YB (-) → BB

Y → BY

V42 = {Y}

Krok 3

j = 3; i = 1..3; k = 1,2

dla i = 1:

V13={ X|X → YZ ; Y ∈ V11, Z ∈ V22} dla k = 1

Y ∈ V12, Z ∈ V31} dla k = 2

(-) → YS (-) → YX (-) → BS (-) → SY

S → BX S → SB

V13 ={S}

dla i = 2:

V23={ X|X → YZ ; Y ∈ V21, Z ∈ V32} dla k = 1

Y ∈ V22, Z ∈ V41} dla k = 2

(-) → SY (-) → XY (-) → XB

X → AY S → SB

V23 ={S, X}

dla i = 3:

V33={ X|X → YZ ; Y ∈ V31, Z ∈ V42} dla k = 1

Y ∈ V32, Z ∈ V51} dla k = 2

(-) → YY (-) → YB

Y → BY

V33 ={Y}

Krok 4

j = 4; i = 1,2; k = 1..3

dla i = 1:

V14={ X|X → YZ ; Y ∈ V11, Z ∈ V23} dla k = 1

Y ∈ V12, Z ∈ V32} dla k = 2

Y ∈ V13, Z ∈ V41} dla k = 3

(-) → YX (-) → YS (-) → BS (-) → SY

S → BX S → SB

V14 ={S}

dla i = 2:

V24={ X|X → YZ ; Y ∈ V21, Z ∈ V33} dla k = 1

Y ∈ V22, Z ∈ V42} dla k = 2

Y ∈ V23, Z ∈ V51} dla k = 3

(-) → SY (-) → XY

X → AY S → SB

V24 ={S, X}

Krok 5

j = 5; i = 1; k = 1..4

dla i = 1:

V15={ X|X → YZ ; Y ∈ V11, Z ∈ V24} dla k = 1

Y ∈ V12, Z ∈ V33} dla k = 2

Y ∈ V13, Z ∈ V42} dla k = 3

Y ∈ V14, Z ∈ V51} dla k = 4

(-) → YX (-) → YS (-) → BS (-) → SY

S → BX S → SB

V15 ={S}

	i=1	i=2	i=3	i=4	i=5
j=1	Y, B y V11	S, X, A x V21	Y, B y V31	Y, B y V41	Y, B y V51
j=2	S yx V12	S, X xy V22	Y yy V32	Y yy V42
j=3	S yxy V13	S, X xyy V23	Y yyy V33
j=4	S yxyy V14	S, X xyyy V24
j=5	S yxyyy V15

Odpowiedź

W zbiorze V₁₅ znajduje się symbol S, z którego można wyprowadzić sprawdzane słowo. Zatem słowo yxyyy należy do języka.

---