Вас просят найти язык, сгенерированный грамматикой G с продукцией
S → aAb | bAa
A → aSa | S | λ
Во-первых, рассмотрим небольшие производные от начального символа S.
S ⇒1 aAb ⇒1 aaSab | aSb | ab
S ⇒1 bAa ⇒1 baSaa | bSa | ba
Сложный шаг связан с рекурсией, сгенерированной правилами A → aSa, S → aAb и S → bAa. Ключ к решению этой проблемы раскрывается при рассмотрении индуктивного определения языка, сгенерированного G:
1. ab ∈ L4
2. ba ∈ L4
3. w ∈ L4 → awb ∈ L4
4. w ∈ L4 → bwa ∈ L4
5. w ∈ L4 → awa ∈ L4
Правила (3)-(5) соответствуют правилам A → aAa, S → aAb и < em>S → bAa в G. Легко видеть, что индуктивное определение и правила G определяют один и тот же язык. Индуктивное определение показывает, что язык G можно построить поэтапно. Начиная с наименьших строк, сгенерированных в G, мы строим все большие и большие наборы строк, соответствующие проблематичным правилам:
L(1) = {ab, ba}
L(n + 1) = {awb, bwa, awa : w ∈ L(n)}
Набор L(1) содержит наименьшие строки, которые можно сгенерировать в G. Набор L(n + 1) содержит строки awb, bwa и awa для каждой строки w ∈ L(n). То есть строки в L(n + 1) соответствуют строкам, полученным применением правил S → aAb, S → bAa и A → aAa один раз для строк в L(n). Остается только построить объединение L(n), которое представляет собой множество:
L = ⋃ {L(n) : n ∈ ℕ}
Чтобы увидеть, что L эквивалентен языку, порожденному грамматикой G, вы можете рассуждать с помощью индукции по длине производных в G. Начиная с наименьших строк, которые можно сгенерировать в G (т. е. ab и ba), работая в обратном направлении, используя соответствующие гипотезы индукции.
person
danportin
schedule
22.11.2011
