Question 1- Write regular expressions to capture the following.

(a) Strings in C. These are delimited by double quotes ("), and may not contain newline characters. They may contain double-quote or backslash characters if and only if those characters are "escaped" by a preceding backslash. You may find it helpful to introduce shorthand notation to represent any character that is not a member of a small specified set.

(b) Comments in Pascal. These are delimited by (* and *) or by { and }.

Question 2- Show(as"circles-and-arrows"diagrams)the finite automata for question 1.

Question 3- (a) Show the NFA that results from applying the construction of Figure to the regular expression letter ( letter | digit )*.

(b) Apply the transformation illustrated by Example 2.14 to create an equivalent DFA.

Question 4- (a) Describe in English the language defined by the regular expression a* (b a* b a* )* . Your description should be a high-level characterization-one that would still make sense if we were using a different regular expression for the same language.

(b) Write an unambiguous context-free grammar that generates the same language.

(c) Using your grammar from part (b), give a canonical (rightmost) derivation of the string baabaaabb.

Question 5- Give an example of a grammar that captures right associativity for an exponentiation operator (e.g., ** in Fortran).

Question 6- Consider the following grammar:

G → S $$

S → A M

M → S |ε 

A → a E | b A A

E → a B | b A|ε

B → b E | a B B

(a) Describe in English the language that the grammar generates.

(b) Show a parse tree for the string abaa.

(c) Is the grammar LL(1)? If so, show the parse table; if not, identify a prediction conflict.

Question 7-Consider the following CFG for floating-point constants, without exponential notation. (Note that this exercise is somewhat artificial: the language in question is regular, and would be handled by the scanner of a typical compiler.)

C → digits . digits

digits → digit more_digits

more_digits → digits|ε

digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Augment this grammar with attribute rules that will accumulate the value of the constant into a val attribute of the root of the parse tree. Your answer should be S-attributed.