Theory of Computing > QUESTIONS & ANSWERS > CS 421 CS421 - Yoshii - HW1 (based on Weeks 1-2a) Warm Up Topics | California State University, Sa (All)

CS 421 CS421 - Yoshii - HW1 (based on Weeks 1-2a) Warm Up Topics | California State University, San Marcos

Document Content and Description Below

California State University, San Marcos CS 421 CS421 - Yoshii - HW1 (based on Weeks 1-2a) Warm Up Topics ================================================================= DUE: Week 2 Friday be... fore midnight (11:55pm) TOTAL: 20 pts ** Name: ==================================================================== Inter questions from week1 notes [2pts per Inter = 8 pts] ----------------------------------------------------------- ##Inter1* Give one sentence which is syntactically incorrect. ## Give another sentence which is syntactically correct but ## is semantically incorrect. ##Inter2* Write all the prefixes of abc: ##Inter4* Give an example of a palindrome using the alphabet {a,b,c}: ##Inter10* Complete {x | x is in A } for A ^ B. Problem 1: Compiler Parts [.5 per prompt = 5 pts] -------------------------------------------------- 1) What are tokens of a programming language? List 2 more types of tokens and give examples from a C++ code. [2pts] Type C++ Example e.g. variable name - Sum 2) What are the two parts of a compiler that we will focus in this class?[3pts] - name one part. - what does it do to/with tokens? - what type of errors does it generate? - name another part. - what does it do to/with tokens? - what type of errors does it generate? Problem 2: Proof by Induction [.5 per prompt = 5 pts] -------------------------------------------------------- We need to get used to using Proof by Induction before we start proving that the language of the grammar is the given one. Prove by induction on n that the sum of 2^k for k = 0 to n = 2^(n+1) -1 for n>=0 Make sure you use exactly the same format as given in the lecture examples. Basis P(0): is true. Assume P(i) is true, AL = AR: for i>=0 Inductive Step P(i) to P(i+1), Show: In terms of AL: in terms of AR: = Conclusion: (state completely) Problem 3: Important Review Questions [2 pts] ---------------------------------------------- What is the difference between an algorithm and a procedure? [1] If the recognizer is an algorithm, the language is If the recognizer is a procedure, the language Submit this file with your answers inserted in black. [Show More]

Last updated: 1 month ago

Preview 1 out of 2 pages

Buy Now

Instant download

We Accept: