Как мы можем доказать это с помощью доказательства индукцией?

Question

Пусть G- следующая грамматика:

S → T⊣

T → ТАТБ | TbTa | ε

Показать, что L (G) = {w⊣ | w содержит равные числа a и b}, используя доказательство индукцией по длине w.

Что можно предположить в этой ситуации?

Answer 1

Для простоты мы можем игнорировать символ S и просто доказать, что T производит равное количество a и b.

Предполагая L = {w | w содержит равные числа a и b}, доказательство состоит из двух частей: 1-Каждая строка с длиной n, которую производит T, находится в L. 2-Каждая строка в L с длиной n может быть получена T.

1) Доказательство 1 просто по индукции. Правило (T → ε) дает равное число a и b, а по индукции правила T → TaTb | TbTa также сохраняет значения a и b.

2) Мы утверждаем, что каждая строка в L с длиной n, которая заканчивается на b, может быть произведена сначала с использованием правила T → TaTb. Доказательство может быть установлено путем нумерации букв. мы даем каждому «a» +1 и каждому «b» -1. Каждая строка в L имеет общий ранг '0' (из-за равного No of a и b's). Каждая строка в L, заканчивающаяся на b, начинается с ранга 0 и достигает ранга +1 перед последним b. Он может достигнуть ранга 0 снова между ними, прежде чем увидеть «a». Здесь мы можем переписать строку w как T1aT2b, в которой T1 и T2 тоже находятся в L, а индукция может быть получена T. (Если ранг w никогда не достигает 0 между ними, это означает, что w начинается с a, поэтому T1 = ε) Доказательство для строк, заканчивающихся на 'a', похоже.