Let us define the language PARENTHESES to be the language of well-formed parenth

Question

Let us define the language PARENTHESES to be the language of well-formed  parenthesis strings.  

PARENTHESES = ( () (()) ()() ((())) (())() ()(()) ()()() … }

(i) Show that this language is nonregular using the Myhill-Nerode theorem

(ii) Show that the pumping lemma cannot be successful in proving that this language is nonregular.

(iii) If we convert “(“ into the letter a and the character “)” into the letter b, show that PARENTHESES becomes a subset of the language EQUAL in    which each word has the property that when read from left to right, there    are never more b’s than a’s

Explanation / Answer

pumping theorem p is the length of pumping lets take the word lets take the word that has p left parethenses and p right parentheses if the language is regular then x y^i z (xyz being parts of a word in the language) for every i larger or equal to zero remains part of the language and |xy| must be less or equal to p so if we say that y is 3 left parentheses and x are the remaining left parentheses, z is what is left if we say that i=2 so we double the 3 left parentheses that are part of y we get a word that has more left parentheses than right so the result of pumping is no longer withing the language so the language is nonregular. p.s. you are not forced to use 3 left parentheses and the remaining for x, you can use variables like n and m for example x is the first m left parentheses, y is the next n parentheses and z is the remaining left (p-n-m) and all the right parentheses this solution is more general and by some teachers is more correct, but i prefer giving the first one as its easier to explain and to understand but you are free to use anyone you can

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.