Let E= (a,b). The Language L = (w *: ne(w) < na(w)} is not regular. (Note:...

 

Transcribed Image Text:

Let E= (a,b). The Language L = (w Σ*: ne(w) < na(w)} is not regular. (Note: na (w) and ns(w) are the number of a's and b's in w, respectively.) To show this language is not regular, suppose you are given p. You now have complete choice of w. So choose t = a+16. Of course you see how this satisfies the requirements of words in the language, there is one more a than b's. Now, answer the following: (a) What does ly) > 0 imply? (b) Since zyl S p, what must y consist of? (e) What must you choose for the substring y in the decomposition ryz? (d) Using i = 0 in the substring decomposition ry'z, what is the resulting string? (e) Is this string in L (that is, are the number of b's still the number of a's?) and is the language regular? Let E= (a,b). The Language L = (w Σ*: ne(w) < na(w)} is not regular. (Note: na (w) and ns(w) are the number of a's and b's in w, respectively.) To show this language is not regular, suppose you are given p. You now have complete choice of w. So choose t = a+16. Of course you see how this satisfies the requirements of words in the language, there is one more a than b's. Now, answer the following: (a) What does ly) > 0 imply? (b) Since zyl S p, what must y consist of? (e) What must you choose for the substring y in the decomposition ryz? (d) Using i = 0 in the substring decomposition ry'z, what is the resulting string? (e) Is this string in L (that is, are the number of b's still the number of a's?) and is the language regular?

Answer rating: 100% (QA)

The image shows a set of questions that relate to the language theory in computer science specifically about regular languages and the use of the pump... View the full answer