Задача по формальным грамматикам

[Levon11]

Добрый день! У меня есть вопрос по формальным грамматикам.

Алфавит = {a,b}
Язык = {любая последовательность, в которой содержится одинаковое кол-во символов a и b}

Я написал следующую грамматику, которую мой преподаватель признал правильной:
S -> aSbS | bSaS | e

Но я не смог сторого доказать правильность данной грамматики.
Подскажите мне метод док-ва...

[PAV]

Метод доказательства должен быть таким. С одной стороны очевидно, что все слова, которые порождает данная грамматика, действительно принадлежат языку. Обратно нужно доказать, что любое слово, которое принадлежит языку, может быть получено таким образом. Это нужно делать индукцией по длине слова. Для слов длины 0 и 2 проверяется непосредственно. Пусть есть более длинное слово. Без ограничения общности считаем, что оно начинается с "а". Значит, оно должно порождаться правилом "aSbS". Нужно только доказать, что в нем найдется такая буква "b", что слово, заключенное между ней и первой "a", принадлежит языку (т.е. количество букв совпадает). Или, если это будет проще, слово после этой буквы (суффикс) принадлежит языку (ясно, что эти дву утверждения равносильны друг другу). Тогда используя предположение индукции мы получаем, что оба этих слова можно вывести.

Добавлено спустя 15 минут 13 секунд:

Ясно, что если все слово начинается с "ab", то в качестве требуемой буквы "b" можно взять именно эту. Аналогично, если все слово заканчивается на "b". Таким образом, содержательный случай - когда и вторая буква всего слова, и последняя - "a".

[незваный гость]

Всё правильно, только мир устроен немного проще. Основное свойство $S$ — в нём равное количество $a$ и $b$.

База индукции у нас есть. Индукционный переход: пусть слово начинается с $a$. Значит, применяем первое правило. Начинаем считать баланс после первого символа (начиная с $0$): если $a$ вычитаем $1$, если $b$ — прибавляем $1$. В какой-то первый момент баланс станет равным $1$ (очевидно, после $b$, иначе, он был положительным до того, а значит — это не первый раз, когда он стал равен $1$). Вот это-то $b$ и есть искомое, к нему и применяем правило.

Осталось только проверить, что и выделенная часть, и хвост содержат равное количество $a$ и $b$. И что их длина уменьшилась.