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.