Формальная грамматика

[Lapana]

Здравствуйте. Помогите, пожалуйста, построить формальную грамматику для языка $L=(a^{n} b^{\left \lfloor \frac{k}{2} \right \rfloor }a^{n} b^{k})_{n,k\geq 0}$

Я знаю, как построить такой язык $L={ b^{\left \lfloor \frac{k}{2} \right \rfloor} a^{n} b^{k}}_{n,k\geq 0}$

$ 1. S \rightarrow \lambda $

$ 2. S \rightarrow Cb $

$ 3. S \rightarrow bCbb $

$ 4. C \rightarrow bACbb $

$ 5. C \rightarrow a $

$ 6. Ab\rightarrow bA $

$ 7. Aa\rightarrow a $

$ 8. Aa \rightarrow Aaa $

Но как породить тот, не понимаю

[arseniiv]

А ничего, что для последнего языка есть грамматика попроще? Контекстно-свободная (когда ваша даже не контекстно-зависимая, such a waste):
\begin{array}{l} S \to B \\ S \to Bb \\ B \to A \\ B \to bBbb \\ A \to \lambda \\ A \to Aa \end{array}
Генерируем сначала «оболочку» из $b$, потом «ядро» из $a$.

А вот язык в вашем вопросе не контекстно-свободный, кажется. Тогда грамматику составьте таким образом: сначала сгенерируйте строку $A^nCA^nB^mDB^{2m}[b]$, меняйте $AB$ на $BA$, превращайте $A,B,C,D$ в $a,b,\lambda,\lambda$, правильно используя контекст. Грамматика неограниченная вышла из-за $AB\to BA$. Контекстно-зависимая не придумалась, но попробуйте пока такую — раз уж вы для второго языка сделали неограниченную (правильность не проверял), почему бы и нет.

[Lapana]

arseniiv в сообщении #947293 писал(а):

А ничего, что для последнего языка есть грамматика попроще? Контекстно-свободная (когда ваша даже не контекстно-зависимая, such a waste):
\begin{array}{l} S \to B \\ S \to Bb \\ B \to A \\ B \to bBbb \\ A \to \lambda \\ A \to Aa \end{array}
Генерируем сначала «оболочку» из $b$, потом «ядро» из $a$.

А вот язык в вашем вопросе не контекстно-свободный, кажется. Тогда грамматику составьте таким образом: сначала сгенерируйте строку $A^nCA^nB^mDB^{2m}[b]$, меняйте $AB$ на $BA$, превращайте $A,B,C,D$ в $a,b,\lambda,\lambda$, правильно используя контекст. Грамматика неограниченная вышла из-за $AB\to BA$. Контекстно-зависимая не придумалась, но попробуйте пока такую — раз уж вы для второго языка сделали неограниченную (правильность не проверял), почему бы и нет.

Что-то такое получилось, но мне кажется Вы придете в ужас. Не особо понимаю, какими принципами необходимо руководствоваться при построении? К сожалению, логика не особо развита.
$ 1. S \rightarrow ACABDBBb $

$ 2. C \rightarrow ACA$

$ 3. D \rightarrow BDBB$

$ 4. AB \rightarrow BA$

$ 5. A \rightarrow a $

$ 6. B\rightarrow b $

$ 7. DB\rightarrow \lambda$

$ 8. DB\rightarrow b$

$ 9. CB \rightarrow b$

[iifat]

arseniiv в сообщении #947293 писал(а):

язык в вашем вопросе не контекстно-свободный

Похоже на то.

arseniiv в сообщении #947293 писал(а):

$A^nCA^nB^mDB^{2m}[b]$

А в чём, стесняюсь спросить, разница? Почему вы считаете, что породить строку нетерминалов проще, чем строку терминалов?
В реальной-то жизни подобные проблемы решаются чем-нить типа грамматик Ван-Вейнгаардена, КС-грамматиками с бесконечным множеством нетерминалов...

-- 20.12.2014, 12:25 --

А, кажется, сообразил. Если построить $I^nJ^nK^{\left \lfloor \frac{k}{2} \right \rfloor}L^k$, потом отсортировать (записать сортировку пузырьком в виде грамматики)...

[arseniiv]

Да, именно сортировка, хотя пузырьковость грамматикой, которая у меня в уме, не гарантируется, и нужды в ней, наверно, и нет. А вот правил $C\to ACA,D\to BDBB$, наверно, лучше не иметь, а иметь правила $C'\to C,D'\to D$. Наверно, то же самое (что-то никак с уверенностью не могу сказать), но так как-то спокойнее.

Lapana в сообщении #949697 писал(а):

но мне кажется Вы придете в ужас

Не приду. А просто поправлю:

Lapana в сообщении #949697 писал(а):

$ 5. A \rightarrow a $

$ 6. B\rightarrow b $

Этого делать не стоит — вы не сможете сортировать терминалы. Всегда можно найти контекст, в котором в них надо превращать.

Lapana в сообщении #949697 писал(а):

$ 7. DB\rightarrow \lambda$

Этого тоже не надо: все сгенерированные $B$ надо в конечном счёте превратить в $b$.

И ещё чисто косметическое:

Lapana в сообщении #949697 писал(а):

$ 1. S \rightarrow ACABDBBb $

Если посмотреть на продукции для $C,D$, можно сократить эту продукцию до $S\to CDb$.

Попробуйте теперь ещё раз.

[Lapana]

arseniiv в сообщении #949942 писал(а):

правила $C'\to C,D'\to D$

A можете пояснить что за $C'$ и $D'$ ?

[arseniiv]

Да, не удался намёк.

Нужно предотвратить ситуацию $\cdots aD\cdots\to\cdots aBDBB\cdots$, после которой новоявленная $B$ влево уже не пойдёт, если не написать ещё кучу правил (к тому же, таких, что без $AB\to BA$ грамматика всё равно не будет контекстно-зависимой — это могло бы быть важно где-нибудь), и аналогичную ситуацию с $C$. По-моему, лучше «деактивировать» продукцию $D\to BDBB$ — просто добавим $D\to D'$, и сортировку делаем только при наличии $D'$, а новые $B$ получаем только из $D$.

(И тут я спутал $D$ с $D'$ по отношению к предыдущему сообщению, но обозначение-то не так важно, если везде одинаковое.)

Ещё подсказка: правил, в которых $A$ заменяется на $a$, три штуки, то же самое с $B$, и по правилу уничтожения для $C'$ и $D'$. Остальные вы уже писали или видели.

-- Вс дек 21, 2014 20:19:51 --

(Оффтоп)

Только сейчас дошло, что самая лучшая подсказка для построения грамматики — пример(ы) вывода. Правда, она и слишком явная, но в этом направлении можно было бы что-нибудь придумать…