Верна ли КС грамматика:

[NiGHTeR]

Вопрос: дан язык $L=\{w\in(a,b,c)^{*}|w=xcy, x\ne y, x,y\in(a,b)^{*}\}$. Нужно построить для него КС грамматику. Сначала я рассматривал язык $L'=\{w\in(a,b,c)^{*}|w=xcy, x=y, x,y\in(a,b)^{*}\}$. Для него легко построить грамматику с правилами $P'=\{S\to{aSb|bSa|c}\}$, S- аксиома.
Далее, рассматриваю правила $P=\{S\to{aSbS_{1}|bSaS_{1}|aSS_{1}b|bSS_{1}a|c}; S_{1}\to{aS_{1}|bS_{1}|a|b}\}$

Тогда в грамматике с такими правилами, в аксиоме S будут накапливаться продукции типа $wSu, w\in{$T$^{*}}, u\in(N\cup{$T$})^{*}$ и u представляет собой w со всевозможными вставками нетерминала$ S_{1}$. А далее, т.к. $S_{1}$ не может перейти в пустое слово, получаем в выводе слово $xcy$, $x\ne y$

правильны ли рассуждения? и если так, как можно обосновать последний абзац строже?

-- Вс ноя 06, 2011 14:07:25 --

В правилах $P$ продукции $S\to{aSS_{1}b|bSS_{1}a}$ - лишние (наверное)

-- Вс ноя 06, 2011 14:43:07 --

Вопрос №2, верно ли что $\{a^{+}b^{+}c^{+}\}\setminus\{a^{n}b^{n}c^{n}, n>0\} = \{a^{n}b^{n}b^{+}c^{+}, n>0\}\cup\{a^{+}b^{+}b^{n}c^{n}, n>0\}$ ?

$a^{+}=aa^{*}$

[cyb12]

Язык $L'$ -- это слова вида $xcx,$ $x\in\{a,b\}^*$? Но грамматике $P'$ удовлетворяет, например, $acb$...

Грамматика $P$ не сможет породить слово $ca$ например. Хотя $x,y$ вроде бы могут быть и пустые. Но вообще вместо $S$ в правых частях можно ввести еще одно $S_2$ которое порождает любое слово над $\{a,b\}^*,$ дабы не делать лишних вставок $S_1.$ И, кроме того, учесть случай, когда $x$ и $y$ могут начинаться с одного символа, но иметь разную длину.