California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii - HW 2A (based on week4a and week4b) RE to FA by Hand

Document Content and Description Below

California State University, San Marcos CS 421   Theory of computing CS421 - Yoshii - HW 2A (based on week4a and week4b) RE to FA by Hand ======================================================... =============== Please always type your answers in black. You can insert pictures into this file. DUE: Week 5 Friday before midnight TOTAL: 20 pts ** Name:   ================================================================================ ------------------------------------------------------------------------------------- Problem 1: Token --> RE (week 4a) [2pts per prompt = 8 pts] -------------------------------------------------------------------------------------- Your first task as a scanner designer is to turn each token into a regular expression. First, describe what you want to write as RE in English. Then, give the RE for it. e.g.   English: 0 or more a's followed by 1 or more b's; shortest is “b” RE:   Alphabet is {a,b}. OK to use e for empty strings. A Describe the language completely in English without using n or m:   RE for it:   B) {w | w has at least one pair of consecutive a's } only a’s and b’s allowed Describe the language completely in English, noting the shortest string:     RE for it -------------------------------------------------- Problem 2: RE -> FA (week 4b) [6 pts] -------------------------------------------------- Not completely specified. Theory version. - (a | b) c Draw a DFA:   - a^* b Draw a DFA:   - a^+ b Draw an NFA (Note it says NFA) without e-moves:   -------------------------------------------------------- Problem 3: Reading NFA (week 4b) [1pt per prompt = 6 pts]   -------------------------------------------------------- Loop on a, b (q0) --------------------a---- (q1) ----b--- ((q2)) First give the Trs for this NFA: 1. Trs(q0, a) = {q0,q1} 2. Trs(q0, b) = { } 3. Trs(q1,b) = {q1, q2} Then give the following Trs for a set of current states: Trs({q0, q1}, b)   What are the possible states you end up in after reading aab?   Should aab be accepted? Why?     [Show More]

Last updated: 1 year ago

Preview 1 out of 2 pages