CS 4100 Exam 1 – Fall 2010 – Steven A. DemurjianName:October 8, 2010Number Points Score1 122 183 154 155 15Total 75Use only one side of the paper and start each problem on a new page!!Please show all work to receive ANY credit!!!!11. (12 points) Derivations and AmbiguityConsider the grammar for regular expressions shown below, where E is the start symbol, E,T, and F are non-terminals, and ‘|’, (, ), x, and ‘*’ are terminals.E −→ E ‘|’ TE −→ TT −→ T FT −→ FF −→ ( E )F −→ F ‘*’F −→ xIn the grammar, ‘|’ refers to the alternation for a regular expression, while ‘*’ refers to closure.The rule T −→ T F represents concatenation.a. (4 points) Develop a leftmost derivation for the string xx(x|x)*b. (4 points) Develop a rightmost derivation for the string xx(x|x)*c. (4 points) Is the grammar ambiguous? Why or why not? Note: Be specific in youranswer!!!2. (18 points) CFGs and Left RecursionConsider the grammar that is given below, where P is the start symbol, L and T are non-terminals, and all other symbols are terminalsoA1−→ a A2aA1−→ d A2dA2−→ A2A3A2−→ A3A2−→ A3−→ A2bA3−→ c A2A3−→ A1bRedesign the grammar given above into an equivalent form that is suitable for top-down parsingby removing any left recursion that exists. In the grammar, a, b, c and d are terminals, andA1, A2, and A3are non-terminals. Make sure that you clearly indicate your results separately,i.e., box the CFG without left recursion with  moves.Extra Page for Problem 23. (15 points total) Regular Languages, Expressions, and NFAsFor parts a and b, you may only use the operators: +, ∗, |, ?, (), and concatenation to constructregular expressions.a. (4 points) Write a regular expression for the language of all strings of {0, 1} whose lengthis a multiple of 3.b. (6 points) Construct a DFA for your answer of part a. Do not use the algorithm thatconverts from regular expression to an NFA to a DFA. Instead, construct your DFAdirectly! Clearly indicate the start state and all final states of your DFA!c. (5 points) Describe using one or two prose sentences the language that is represented bythe regular expression: (0 | 1)∗0(0 | 1)(0 | 1).4. (15 points) FIRST and FOLLOW for CFGsExpressions in the Lisp functional programming language are formed using nested parenthesesand operators which apply to exactly two operands. Below are some example Lisp expressionswith their infix equivalents:(= x (+ a (* b 5))) x = (a+(b*5))(= y (- (* d (+ a 3)) (/ 8 d))) y = (((a+3)*d)-(8/d))A context-free grammar for lisp expressions is as follows:E --> ( = id L )L --> ( A F F )L --> ( M F F )F --> int | id | LA --> + | -M --> * | \Note that for simplicity, id and int represent tokens for valid identifiers or integer digits.Using this grammar, compute FIRST for E, L, and F, and FOLLOW for L, F, A, and M.5. (15 points) Your work for the IC Graphics company and have been asked to assist in thedevelopment of a CAD/CAM mechanical design system. The system supports the design ofsimple mechanical parts that are constructed from two different shapes, blocks and cylinders,that may or may not contain a hole, and in turn may be combined with each other by placingshapes next to one another or on top of one another. Your responsibility at IC Graphics is todevelop a lexical analyzer and parser for representing legal combinations of blocks, cylinders,and holes into simple mechanical parts. There are four different tokens, blocks/BLOCK,cylinders/CYL, blocks with holes/H-BLOCK, and cylinders with holes H-CYL. Example blocksare B1, B10, B23, B117, etc., chulinders are Ca, Cb, Cz, Cab, Ccc, etc., and holes within ablock or cylinder are parenthesized, such as (B25), (Caa), (Ci), etc. Design a context freegrammar that combines BLOCK, CYL, H-BLOCK, and C-BLOCK (which we’ll call objects)using two construction operations: pile-on, represented by square brackets [ ], and next-to,represented by angle brackets < >. The operation pile-on takes two or more objects andplaces one on top of another. The operation next-to takes two or more objects and placesthem adjacent to one another. For example:B11[B11 Ca (B2)] yields Ca(B2)and<Cb (Cd) B6 Ch> yields Cb (Cd) B6 ChIn addition, the objects that are combined may also be the result of a pile-on or next-toconstruction. This leads to the following possibilities:[B11 <B5 C8>] yields B11B5 C8and<[B4 B2] (C5) [C2 B1]> yields B4 C2B2 (C5) B1The nesting can be performed to any desired level of depth. Your task is to develop a contextfree grammar that can represent all legal combinations of objects, using pile-on [ ] and next-to< >, to any level of nesting depth. Note that ‘[’, ‘]’, ‘<’, and ‘>’ are all tokens.Extra Page for Problem