Politechnika Rzeszowska

Wydział Elektrotechniki i Informatyki

Katedra Informatyki i Automatyki

Języki, automaty i obliczenia

PROJEKT cz. I

Gramatyki i języki bezkontekstowe

Wykonała: Urbańska Anna

II EF-DI

Rzeszów 2012

Temat projektu:

Dla danej gramatyki bezkontekstowej wyprowadzić język przez nią generowany.

Dane:

Gramatyka G=<{S, A, B, a,b}, {a, b}, P, S > o następujących regułach produkcji:

_{1 2 3}

S → aA | SA | bB

_{4 5 6}

A → aB | a | b

_{7 8}

B → Λ | bB

Wyprowadzenie języka generowanego przez powyższą gramatykę

_{2 *2 1 4,5,6 *8 7}

S → SA → SAⁿ → aAⁿ⁺¹ → a(aB+a+b)ⁿ⁺¹ → a(ab^kB+a+b)ⁿ⁺¹ → a(ab^k+a+b)ⁿ⁺¹ = a(ab^k+b)ⁿ⁺¹

^{n=0,1,… k=0,1,… n,k=0,1,…}

³

_{4,5,6 *8 7}

bBAⁿ → bB(aB+a+b)ⁿ → bb^mB(ab^kB+a+b)ⁿ → bb^m(ab^k+a+b)ⁿ = b^m+1(ab^k+b)ⁿ

m,k=0,1,... n,m,k=0,1,...

Odpowiedź

Język generowany przez podaną gramatykę:

L(G)= {a(ab^k+b)ⁿ⁺¹ + b^m+1(ab^k+b)ⁿ, n,m,k = 0, 1, 2, ...}

2

---