Question

Let B be the set of all strings of balanced brackets. Let T be the subset of B of strings w such that if we reverse w and interchange left and ]s, then we get back w. For example, the strings ((())) and (()()) are in T, but ()(()) is not. Use the Pumping Lemma to show that T is not regular

Answer 1

Assume that T is regular then by pumming lemma, there is some pumping length . n such that any word w in T of length at least n can be split into w=xyz satisfy the following conditions:

|xy|<=n

|y|>0

`xy^(i)z`∈
`T` for all
`i`≥0

We let w be the word with n left parentheses, followed by n right parentheses and if they interchanged they still remain balanced Then by the first condition we know that y consists only left parenthesis. By the second condition we know that y is nonempty . So the string xyyz must have more left parentheses tan right parenthesis and vice versa . therefore it must be unbalanced , so the third condition of the pumping lemma fails, Hence T cannot be regular