CSC 320 Midterm: CSC 320 UVic Midterm11
Document Summary
Put your name on every page of the exam. You should have 9 pages includ- ing this header page. If you need more space you can write on the backs of the pages. For parts (a), (b), (c) and (d) below, you must choose four different languages from the ve giv en here and are required to nd a regular expression, a context-free grammar, a dfa, and a pda for them respectively. L1 = { w w : w { a, b }* } L2 = { w { 0, 1 }* : w contains 01001 } L3 = { a p bq cr d s. L4 = { u u r v v r : u { 0, 1 }*, v { 0, 1 }+ } L5 = { w { a, b }* : w has both abba and baab as substrings } : ( p + q) = (r + s), p, q, r, s 0 }