Является ли этот контекстно-свободный язык обычным?

Язык, связанный с грамматикой, не является регулярным. Остальная часть поста посвящена доказательству этого утверждения.

Во-первых, обратите внимание, что L(T) = {w over {0,1} | w contains equal number of 0s and 1s}.

Вы легко можете это доказать.

Доказательство идеи. (==>) Предположим, w в L(T). Тогда, очевидно, имеет одинаковое количество нулей и единиц.

(<==) Предположим, что w содержит равное количество нулей и единиц. По индукции покажем, что w выводится из T. Если |w|<=2, то он, очевидно, выводится из T. Предположим, для индуктивной гипотезы, что все строки длины k (четной длины) с равным количеством нулей и единиц выводятся из T. Пусть w будет иметь длину k+2. Если первый и последний символы w совпадают (оба 0 или оба 1), применить результат T -> TT; первая и последняя части выводятся из T с помощью индуктивной гипотезы; здесь мы используем очевидное свойство: если w[0]=w[|w|-1], то существует индекс i, такой, что w[0..i] и w[i+1..|w|-1] оба находятся в L(T), и оба выводятся из T по индуктивной гипотезе. В противном случае, если первый и последний символы w не совпадают, используйте T -> 0T1 или T -> 1T0; результирующая строка имеет длину k и выводится из T по индуктивной гипотезе. QED.

Теперь язык грамматики - это набор строк, которые могут быть сгенерированы S. Обратите внимание, что S генерирует строки (терминалов и переменных) в форме (T+1)*1T. Другими словами, для любой строки терминалов w, выводимой с помощью грамматики, должен быть случай, который S =>* α =>* w, где α находится в (T+1)*1T.

Теперь должно быть очевидно, что набор всех возможных терминалов, которые могут быть сгенерированы S, характеризуется регулярным выражением (L(T)* + 1)*1L(T)*. (Вы можете прийти к этому, проверив набор строк терминалов, которые могут быть сгенерированы из (T+1)*1T.)

Вы можете упростить выражение для L(S): (L(T)+1)*1L(T)=(L(T)+1)*, потому что язык 1L(T) является подмножеством языка (L(T)+1)^2. Таким образом, L(S) = (L(T)+1)*, язык, состоящий из двоичных строк, содержащих как минимум столько же единиц, сколько нулей.

Этот язык нестандартный. Вы можете доказать это, используя лемму о перекачке.

Доказательство. Предположим, для противодействия, что L(S) регулярно. Затем, согласно лемме о накачке, существует n>0 такое, что каждый w из L(S) длины не менее n может быть разбит на w=xyz так, что:

1. |xy| <= n,
2. y непусто,
3. для всех k >= 0, xy^ky в L(S).

Пусть w=0^n1^n будет строкой длины m=2n из L(S). (В лемме говорится о всех достаточно длинных строках из L(S), поэтому мы можем выбрать любую строку, которая нам нравится, и при этом сохранить свойства.) Пусть w=xyz будет разбиением, существующим по лемме. Очевидно, поскольку m=2n и |xy|<=n, y состоит только из 0 (и по крайней мере один 0, поскольку y не пуст).

Очевидно, что xy^2z имеет больше нулей, чем единиц, и поэтому не входит в L(S). Это противоречит лемме о накачке. Таким образом, L(S) не является регулярным. QED.