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

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 year ago

Preview 1 out of 2 pages