COMP 335 Study Guide - Final Guide: Turing Machine, Jyj, Jacques Lacan

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 335
• Professor: Nematollaah Shiri

Document Summary

Comp 335 introduction to theoretical computer science. Submission through moodle due on thursday nov. 29th at 23:55. That means, while the what is important, the why is absolutely essential. Show steps of your solution for the full mark. Total mark is 60: [10 points] show that the family of context-free languages are closed under each of the following operations. (a). Homomorphism. (note: lr = {wr : w l}, for any language l. ) If and are alphabets, a homomorphism h is a function from to , that is h replaces a single symbol in to a string over . For each language, if it is cf, give a cfg that generates it; otherwise prove your claim. (a). La = {w : w 6= uu, u l((a + b) )} Hint 1: note that la contains every string of length odd and certain strings of length even.