Politechnika Rzeszowska

Wydział Elektrotechniki i Informatyki

Katedra Informatyki i Automatyki

Języki, automaty i obliczenia

PROJEKT cz. IV

Gramatyki deterministyczne i zupełne

Wykonał: Adam Kubicki

II EF-DI

Rzeszów 2012

Temat projektu:

Daną gramatykę regularną, niedeterministyczną i niezupełną przekształcić do postaci deterministycznej, a następnie do postaci zupełnej.

Dane:

Gramatyka G=<{S,K,L,M, 0, 1,2}, {0,1,2}, P, S > o następujących regułach produkcji:

S → 0K | 0L | 2S

K → 1M|1

L → 0M | 1L

M → 2K | 2M

Zamiana do postaci deterministycznej :

Krok pierwszy :

Dodaję nową regułę produkcji N → Λ i otrzymuję gramatykę postaci :

Gramatyka G’=<{ S,K,L,M,N, 0, 1,2}, {0, 1,2}, P’, S > o następujących regułach produkcji:

S → 0K | 0L | 2S

K → 1M|1N

L → 0M | 1L

M → 2K | 2M

N → Λ

Graf deterministyczny:

Gramatyka Deterministyczna :
Gramatyka G’’=<{S₀, S₁, S₂, S₃, S₄, S₅, S₆,0, 1, 2}, {0, 1, 2}, P’’, S₀ > o następujących regułach produkcji:

S₀ → 0S₁ |2S₀

S₁ → 0S₂ | 1S₃

S₂ → 2S₄

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

S₄ → 1S₆ | 2S₄

S₅ → 0S₂ | 1S₅

S₆ → 2S₄ | Λ

Graf zupełny:

Gramatyka deterministyczna zupełna:

Gramatyka G’’’=<{S₀, S₁, S₂, S₃, S₄, S₅, S₆, P ,0, 1, 2}, {0, 1, 2}, P’’’, S₀ > o następujących regułach produkcji:

S₀ → 0S₁|1P | 2S₀

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

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

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

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

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

S₆ → 0P |1P | 2S₄ | Λ

P → 0P | 1P | 2P