10.12.12 Rzeszów

• Politechnika Rzeszowska

• Wydział Elektrotechniki i Informatyki

• Katedra Automatyki i Informatyki

Języki, Automaty i Obliczenia

• PROJEKT (część IV)

Gramatyki deterministyczne i zupełne.

• Kotowicz Mateusz (127132)

• P07 / 2EF-DI

Wstęp

Przekształcić gramatykę regularną do postaci deterministycznej i zupełnej.

Dane

G = < {S, K, L, M, 0, 1, 2}, {0, 1, 2}, P, S >

S → 0K | 2L | 0 | 2S

K → 2M | 1K | 2

L → 0L | 0

M → 2

• Rozwiązanie

Po pozbyciu się reguł końcowych gramatyka ma postać:

G' = < {S, K, L, M, N, 0, 1, 2}, {0, 1, 2}, P', S >

S → 0K | 2L | 0N | 2S

K → 2M | 1K | 2N

L → 0L | 0N

M → 2N

N → Λ

Po zamianie na postać deterministyczną gramatyka ma postać:

G'' = < {S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈, 0, 1, 2}, {0, 1, 2}, P'', S₁ >

S₁ → 0S₂ | 2S₃

S₂ → 1S₄ | 2S₅ | Λ

S₃ → 0S₆ | 2S₃

S₄ → 1S₄ | 2S₃

S₅ → 2S₇ | Λ

S₆ → 0S₈ | 1S₄ | 2S₅ | Λ

S₇ → Λ

S₈ → 0S₈ | Λ

Po zamianie na postać zupełną gramatyka ma postać:

G''' = < {S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈, P, 0, 1, 2}, {0, 1, 2}, P''', S₁ >

S₁ → 0S₂ | 1P | 2S₃

S₂ → 0P | 1S₄ | 2S₅ | Λ

S₃ → 0S₆ | 1P | 2S₃

S₄ → 0P | 1S₄ | 2S₃

S₅ → 0P | 1P | 2S₇ | Λ

S₆ → 0S₈ | 1S₄ | 2S₅ | Λ

S₇ → 0P | 1P | 2P | Λ

S₈ → 0S₈ | 1P | 2P | Λ

P → 0P | 1P | 2P

Odpowiedź

Gramatyka G''' ma postać deterministyczną i zupełną.

---