Как мне определить язык, генерируемый этой контекстно-свободной грамматикой?

Question

Я имею дело со следующей грамматикой:

G = ( {S, A}, {a, b}, P, S ) 
P = { S -> aAb, S -> bAa, 
A -> aSa, 
A -> S, 
A -> epsilon}

Мне нужно выяснить L (G).Дело в том, что я понял, что слова в грамматике имеют вид: начинается с а и заканчивается на б, или начинается на б и заканчивается на а, а между этими буквами одна из комбинаций: ab, ba, aabaABAA;затем следующее слово формируется путем вставки одной из этих 4 комбинаций между a и b посередине ... но как я могу выразить это формально?Я имею в виду, насколько я мог сказать, L (A) = a ^ n S a ^ n, и если w принадлежит L (G), то обратное w также принадлежит L (G).Я пытался выразить это как регулярное выражение, но не смог ... может кто-нибудь помочь?

Спасибо.

Answer 1

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

Вы можете заметить, что, поскольку L состоит только из {a, b}, вы можете использовать его мощность. Мы видим, что язык имеет форму aAb или bAa или aAa, за исключением того, что aAa не может находиться в начале и конце слова.

Итак, давайте использовать это, единственное, чего нам не хватает, так это комбинации bAb A, которая может генерировать почти все (слова | w | = 2k и | w |> = 2), но слова, где позиция b соответствует позицииb с обратной стороны

Формально

Извините за мои навыки работы с текстом и мое формальное выражение

должна быть какая-то ошибка, потому что у меня не было так многовремя подумать об этом, но это может быть какой-то способ, как продолжить, это домашнее задание, так что все в порядке, подумайте об этом!:)

Answer 2

сгенерированный язык: (a) ⁿ (b) ^m Были n> = m

Answer 3

Вас просят найти язык, сгенерированный грамматикой 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 и S → bAa in 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 * +1066 * (п). То есть строки в L (n + 1) соответствуют строкам, полученным с применением правил S → aAb , S → bAa и A → aAa один раз для строк в L (n). Осталось только создать объединение L (n), которое представляет собой набор:

L = ⋃ {L(n) : n ∈ ℕ}

Чтобы увидеть, что L эквивалентен языку, сгенерированному грамматикой G , вы можете по индукции поспорить с длиной производных в G . Начиная с наименьших строк, которые можно найти в G (т. Е. ab и ba ), работая в обратном направлении, используя соответствующие индукционные гипотезы.

Answer 4

Я пытался выразить это как регулярное выражение, но не смог

Этот язык "вероятно" не является регулярным. Языки без контекста являются более сложными / мощными, чем регулярные выражения.

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

Некоторые подсказки, несколько свойств, которые вы легко можете увидеть:

1. Наименьшая строка имеет размер не менее 2.

2. Размер строки четный.

3. Количество b <<чем a. </p>

Если вы берете A -> aSa и сравниваете слово с его обращенной версией, шаблон должен быть виден Если вы включите исключенное правило, шаблон немного изменится ...