EECS 2001 Study Guide - Final Guide: Empty String, Noam Chomsky, Context-Free Grammar

196 views3 pages

Document Summary

Instructions/information: (i) solve multiple choice problems by marking appropriate true or false. (ii) this exam is worth 40%, distributed as shown. (iii) this sample exam does not cover all the subjects that will appear on the nal exam. Which of the following statements concerning pdas are true and which are. Let m be an arbitrary tm and w a string of input symbols. Give an example of a grammar that is not in chomsky normal form (cnf). Show that a tm with {0, 1} as its set of input symbols, computes in nitely many di erent integer functions. Let g0 and g1 be two context-free grammars with the same terminal and non- terminal symbols, and such that if a is a production in g0, then can be derived from a in g1. Justify your answers. (a) l(g0) = l(g1), (b) l(g0) l(g1), (c) l(g0) l(g1) = .