subject: computer science-theory of computing

Turn in your solution as a plain text file, listing the answers for L through L. For each language, specify the location in the diagram that is closest to the center and shows which language sets are not included. For example, ab SD, D, and CFLs, but the best answer is CFLs/RLs (ab is context-free but not regular). Do not forget to affirm the honor code.

-Name, cardinality, and example language -SD, or the great beyond Le if it can be Le if there is a reduction from -H to L I-SD = 3; -HE-SD : L(M) = (a) -SD) semidecided by a TM Le ring if L can be semidecided by a TM; if L SD Le ring if it can be proved to be not can be generated by an unrestricted grammar. ISD = X Nondeterminism: Nondeterministic TMs and semidecidable by a reduction from H; if L HE SD/D; a'b'e SD E SD/D deterministic TMs recognize the same set of languages. Memory: unrestricted access, unlimited Le ring if Le SD and LE SD; if L can be LED. If it satisfies the requirements for Rice's decided by a TM; if L can be generated by ID = N. theorem; if it can be proven to not be decidable a context-sensitive grammar. Nondeterminism: The equivalence of abec D/CFL by a reduction from H. deterministic and non-deterministic LBA is an a'b'eD; Memory: Unrestricted access to infinite memory, or to memory size = 1W + 2 for LBA recognizing open question Cering if it can be accepted by IS PDA; if it can be generated by a CFLS CFG: if it is the intersection of a CFLSI = LE CFLs if L lacks properties CFL and an RL. "V" e CFLS/RLS guaranteed by the CF pumping Nondeterminism: The set of a'b' e CFL theorem. languages recognized by Memory: PDA require an infinite stack. deterministic PDA are a proper subset of those recognized by pondeterminis.PRA. LE RLS it can be described by a regular RLS expression; accepted by an IRLS - X LERLs if L lacks properties FSM; or has a finite number a'b' e RLS guaranteed by the RL pumping of indistinguishability theorem; or it has an infinite equivalence classes number of indistinguishability Nondeterminism: NDFSMS equivalence classes and DFSMs recognize the Memory: FSMs require none same set of languages. Onion Diagram lab Submit a plain text file indicating where the 20 languages listed below should be placed on the onion diagram. Your answers should follow the format shown in blue for La L = { : IL(M)1 % 3 = 2) L: = : w(w e L(M) and (w % 30) 1. = : 13x1 #(w) > I = {}, L. = {W: #.(W) > #(W) > S = {b}. Le = {w: w starts with a and ends with b ) L = : L(M) contains a string starting with a and ending with b) Lu = { the length of every string in L(M.), and WEL(M) } I = {abes). ... - : 0 L(M)) L. { : L(M)=L(M,) ) L = {

: Pis syntactically correct Python source code.) 13. = : where Pis syntactically correct Python source code, and w is an arbitrary string in E". When P is executed by a Python interpreter, it will halt on input w) L2: =