2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Формальная грамматика
Сообщение15.12.2014, 20:46 
Здравствуйте. Помогите, пожалуйста, построить формальную грамматику для языка $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 $

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

 
 
 
 Re: Формальная грамматика
Сообщение16.12.2014, 00:18 
А ничего, что для последнего языка есть грамматика попроще? Контекстно-свободная (когда ваша даже не контекстно-зависимая, 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$. Контекстно-зависимая не придумалась, но попробуйте пока такую — раз уж вы для второго языка сделали неограниченную (правильность не проверял), почему бы и нет.

 
 
 
 Re: Формальная грамматика
Сообщение20.12.2014, 01:39 
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$

 
 
 
 Re: Формальная грамматика
Сообщение20.12.2014, 04:12 
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$, потом отсортировать (записать сортировку пузырьком в виде грамматики)...

 
 
 
 Re: Формальная грамматика
Сообщение20.12.2014, 17:26 
Да, именно сортировка, хотя пузырьковость грамматикой, которая у меня в уме, не гарантируется, и нужды в ней, наверно, и нет. А вот правил $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$.

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

 
 
 
 Re: Формальная грамматика
Сообщение21.12.2014, 03:33 
arseniiv в сообщении #949942 писал(а):
правила $C'\to C,D'\to D$


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

 
 
 
 Re: Формальная грамматика
Сообщение21.12.2014, 17:15 
Да, не удался намёк. :lol:

Нужно предотвратить ситуацию $\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 --

(Оффтоп)

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group