Politechnika Rzeszowska

Wydział Elektrotechniki i Informatyki

Katedra Informatyki i Automatyki

Języki, automaty i obliczenia

PROJEKT cz. III

Cocke-Younger-Kasami’s algorithm

Wykonał: Adam Kubicki

II EF-DI

Rzeszów 2012

Temat projektu:

Sprawdzić algorytmem Cocke’a – Younger’a – Kasami’ego czy dane słowo należy do języka.

Dane:

Gramatyka G=<{S, Z, X, Y, x ,y}, {x, y}, P, S > o następujących regułach produkcji:

S → Yy | Xy

Y → yX | yx | Zx

X → Xy | yx

Z → y | x

Gramatyka w postaci Chomsky’ego G’=<{S,Y,X,Z,A,B,x,y},{x,y},P’,S>

o następujących regułach produkcji:

S → YA | XA

Y → AX | AB | ZB

X → XA | AB

Z → y | x

A→y

B→x

Wybrane słowo 5-cio literowe należące do języka:

x = yxyyy

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2
3
4
5

Postępowanie wg algorytmu:

V₁₁ = {X | X → y} = {A, Z}

V₂₁ = {X | X → x} = {B,Z}

V₃₁ = {X | X → y} = {A,Z}

V₄₁ = {X | X → y} = {A,Z}

V₅₁ = {X | X → y} = {A,Z}

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

i = 1, k = 1

V₁₂ = {X | X → YZ; Y є V₁₁, Z є V₂₁}

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y
3
4
5

V₁₁ × V₂₁

{A, Z} × { B, Z }

X,Y → AB

(-) → AZ

(-) → ZB

(-) →ZZ V₁₂ = { X,Y}

i = 2, k = 1

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-
3
4
5

V₂₂ = {X | X → YZ; Y є V₂₁, Z є V₃₁}

V₂₁ × V₃₁

{B,Z} × {A,Z}

(-) →BA

(-) →BZ

(-) →ZA

(-) →ZZ

V₂₂ = {∅}

i = 3, k = 1

V₃₂ = {X | X → YZ; Y є V₃₁, Z є V₄₁}

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-
3
4
5

V₃₁ × V₄₁

{ A,Z } × { A,Z }

(-) →AA

(-) →AZ

(-) →ZA

(-) →ZZ

V₃₂ = {∅}

i = 4, k = 1

V₄₂ = {X | X → YZ; Y є V₄₁, Z є V₅₁}

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-	-
3
4
5

V₄₁ × V₅₁

{A,Z} × {A,Z}

(-) →AA

(-) →AZ

(-) →ZA

(-) →ZZ

V₄₂ = {∅}

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

i = 1

V₁₃ = {X | X → YZ; Y є V₁₁, Z є V₂₂ ; k = 1

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-	-
3	S,X
4
5

X | X → YZ; Y є V₁₂, Z є V₃₁} k = 2

V₁₁ × V₂₂ v V₁₂ × V₃₁

{A, Z} × {∅} v {X,Y} × {A,Z}

(S,X) → XA

(-) → XZ

(S) → YA

(-) → YZ

V₁₃ = {S,X}

i = 2

V₂₃ = {X | X → YZ; Y є V₂₁, Z є V₃₂; k = 1

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-	-
3	S,X	-
4
5

X | X → YZ; Y є V₂₂, Z є V₄₁} k = 2

V₂₁ × V₃₂ v V₂₂ × V₄₁

{B,Z} × {∅} v {∅} × {A,Z}

(-) → {∅}

V₂₃ = {∅}

i = 3

V₃₃ = {X | X → YZ; Y є V₃₁, Z є V₄₂; k = 1

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-	-
3	S,X	-	-
4
5

X | X → YZ; Y є V₃₂, Z є V₅₁} k = 2

V₃₁ × V₄₂ v V₃₂ × V₅₁

{A,Z} × {∅} v {∅} × {A,Z}

(-) → {∅}

V₃₃ = {∅}

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

i = 1

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-	-
3	S,X	-	-
4	S,X
5

V₁₄ = {X | X → YZ; Y є V₁₁, Z є V₂₃; k = 1

X | X → YZ; Y є V₁₂, Z є V₃₂; k = 2

X | X → YZ; Y є V₁₃, Z є V₄₁} k = 3

V₁₁ × V₂₃ v V₁₂ × V₃₂ v V₁₃ × V₄₁

{A, Z} × {∅} v {X,Y } × {∅} v {S,X} × {A,Z}

(-)→ SA

(-) → SZ

S,X → XA

(-) → XZ

V₁₄ = {S,X}

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-	-
3	S,X	-	-
4	S,X	-
5

i = 2

V₂₄ = {X | X → YZ; Y є V₂₁, Z є V₃₃; k = 1

X | X → YZ; Y є V₂₂, Z є V₄₂ ; k= 2

X | X → YZ; Y є V₂₃, Z є V₅₁} k = 3

V₂₁ × V₃₃ v V₂₂ × V₄₂ v V₂₃ × V₅₁

{B,Z} × {∅} v {∅} × {∅} v {∅} × {A,Z}

(-) →{∅}

V₂₄ = {∅}

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

j/i	1	2	3	4	5
1	A, Z	B, Z	A, Z	A, Z	A, Z
2	X,Y	-	-	-
3	S,X	-	-
4	S,X	-
5	S,X

i = 1

V₁₅ = {X | X → YZ; Y є V₁₁, Z є V₂₄; k = 1

V₁₅ = X | X → YZ; Y є V₁₂, Z є V₃₃; k = 2

V₁₅ = X | X → YZ; Y є V₁₃, Z є V₄₂; k = 3

V₁₅ = X | X → YZ; Y є V₁₄, Z є V₅₁} k = 4

V₁₁ × V₂₄ v V₁₂ × V₃₃ v V₁₃ × V₄₂ v V₁₄ × V₅₁

{A, Z} × {∅} v {X,Y} × {∅} v {S,X} × {∅} v {S,X} × {A,Z}

(-) →SA

(-) →SZ

(S,X) →XA

(-) →XZ

V₁₅ = {S,X}

_*

V₁₅ → x₁₅

_*

S → yxyyy

Odp. Słowo „yxyyy” należy do języka i można go wygenerować z symbolu początkowego S, ponieważ symbol S znajduje się w ostatniej komórce tabeli utworzonej podczas działania algorytmu.