COMP 335 Study Guide - Final Guide: Regular Grammar, Regular Language, Regular Expression
2 Dec 2018
School
Department
Course
Professor
Document Summary
Comp 335 introduction to theoretical computer science. That means, while the what is important, the why is absolutely essential. Show the steps of your solution for the full mark. Total mark is 70: (10 points) let l be any regular language over an alphabet . Using l, we de ne chop(l) = {w : x, y, z , xyz l, w = xz}. Name your states q1, q2, . (b) use nfa to dfa conversion procedure (theorem 2. 2) to convert your nfa from the previous part to a dfa. In words, this operation extracts all characters at positions divisible by 5. We can naturally extend this operation to languages: if l is a language, f if th(l) = {f if th(w) : w l}. Prove that if l is regular then f if th(l) is also regular: (10 points) let = {a}.
