(20 points) State which of the following languages are (1) not context-free (2)
ID: 3599749 • Letter: #
Question
(20 points) State which of the following languages are (1) not context-free (2) context-free but not regular or (3) regular and context-free. If a language is not context-free then give a string, s, for that language that could be used in a proof using the Pumping Lemma for context-free languages.
A = { bmw | m 0 and w Î {a, b}* and |w| = m}
B = { (ab)n(cb)m | m, n > 0 and m n}
C = {(ab)n(ab)m| m, n > 0}
D = { wbnw | n 0, w Î {a, b}* }
E = { w | w is in {a, b, c}* and w has an equal number of a’s, b’s and c’s}. So abbcac is in E.
Explanation / Answer
A = { bmw | m 0 and w Î {a, b}* and |w| = m}
Not Regulat, because we need to count number of b's and we do not have infnite memory in FA.
This is Not Contex Free because we do not know the end of b, so that we can mesaure length of W
B = { (ab)n(cb)m | m, n > 0 and m n}
Not Regular and Not Context Free
C = {(ab)n(ab)m| m, n > 0} : Regular and Context free
D = { wbnw | n 0, w Î {a, b}* } : Not contex free
E = { w | w is in {a, b, c}* and w has an equal number of a’s, b’s and c’s}. So abbcac is in E. : Not context free
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.