Некоторые свойства грамматик.

Date: 2015-10-07; view: 431.

Понятие выводимости

Отношение Þ_G непосредственного вывода на множестве (T È N)* – j Þ_G y означает, что y непосредственно выводимо из j для грамматики G=(T, N, P, S), т.е, если abg – цепочка из множества (T È N)* и b ® d – правило из Р, то abg Þ_G adg

Транзитивное замыкание отношения Þ_G⁺ (нетривиальный вывод за один и более шагов) – j Þ_G⁺ y означает, что y выводимо из j нетривиальным образом (возможно за несколько шагов).

Рефлексивное и транзитивное замыканиеотношения Þ_G^* (вывод за нуль и более шагов) – j Þ_G^* y означает, чтоy выводимо из j.

Пусть Þ^k – k-я степень отношения Þ, тогда, если a Þ^k b, то существует последовательность a₀a₁a₂a₃ ... a_k из к+1-й цепочки: a=a₀, a₁, ... a_{i -1} Þ a_i,, где 1≤i≤k и a_k=b.

Например, грамматика, порождающая язык {0ⁿ1ⁿ | n≥0} (| – где), имеет вид:

G₀=({0,1}, {S}, S, P),

где набор правил определяется следующим образом: P={S→0S1, S→ε};

грамматика, порождающая язык {a^mbⁿ | m,n ≥ 0}, имеет вид: G₁=({a,b}, {S,A,B}, S, P),

где набор правил определяется, как P={S→AB, A→aA, A→ε, B→bB, B→ε}.

Например, выводы для грамматики G1=({0, 1}, {A, S}, S, P):

S порождает: S Þ 0A1 Þ 00A11 Þ 0011

i-тая степень отношения: S Þ¹ 0A1; S Þ² 00A11; S Þ³ 0011

транзитивное замыкание отношения: S Þ⁺ 0A1; S Þ⁺ 00A11; S Þ⁺ 0011

рефлексивное и транзитивное замыкание отношения: S Þ^* S; S Þ^* 0A1; S Þ^* 00A11; S Þ^* 0011

где 0011Ì L(G1) – принадлежит языку L грамматики G1

1. Эквивалентность грамматик – когда различные грамматики порождают один и тот же язык, т.е. грамматики G1 и G2 будут эквивалентными, если L(G1) = L(G2).

Например, G1=({0,1}, {A,S}, S, P1) и G2=({0,1}, {S}, S, P2)

где P1: S → 0A1

P2: S → 0S1 | 01 (| – знак или)

0A → 00A1

A → ε

эквивалентны, так как обе порождают язык L(G1)=L(G2)={0ⁿ1ⁿ | n>0}

Несмотря на эквивалентность определяемых языков, одна грамматика может быть значительно удобнее другой, с точки зрения ее использования в компиляторе.

2. Определение грамматик не накладывает никаких ограничений на количество нетерминалов в левой части правил.

Например, грамматика G=({a,b,c},{S,B,C},S,P), где P содержит следующие правила: P={S→aSBC,S→abC,CB→BC,bB→bb,bC→bc,cC→cc}, порождает язык {aⁿbⁿcⁿ | n≥1}.

В грамматике G=({0,1},{А,S},S,P), где P={S → 0A, 0A → 00A1, S → ε} – левая часть одного из правил содержит пару из терминального и нетерминального символа.

Эквивалентная ей грамматика G1=({0,1}, {A,S}, S, P1), где

P1: S → 0A1

0A → 00A1

A → ε