C S 341 Midterm: CS 341 Midterm2PracticeAnswers
Document Summary
Use extra paper to determine your solutions then neatly transcribe them onto these sheets. You may use any claim we proved in class as a theorem. But make sure that you only use such a claim when it is exactly what you need. Make sure, if you say that a language is context free, that you show that it is not also regular. (a) {w {0, 1}* : k 0 and w is a binary encoding (leading zeros allowed) of 2k+1}. L = 0* (10 10*1). (b) {a*b*c* - {anbncn : n 0}}. L = {aibjck : i, j, k 0 and i j or j k}. Pda shown in example 12. 8 except that the top branch should not be present. If l were regular, then l would also be regular. L = {w {a, b, c}* with letters out of order} {anbncn : n 0}.
