Theory of Computing > QUESTIONS & ANSWERS > CS 421 Theory of computing CS421 HW 2A (based on week4a and week4b) RE to FA by Hand | California S (All)

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

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: 7 months ago

Preview 1 out of 2 pages

Buy Now

Instant download

We Accept: