HW 3 – Finite State Automata, RegularExpressions, and GrammarsCS 421 – Fall 2006Revision 1.2Assigned Wednesdy, October 25, 2006Due Wednesday Novenber 8, 2006, 9:00 AMTo be turned in at 2106 Siebel Center, office of Andrea WhitesellExtension 48 hours (20% penalty)1 Change Log1.0 Initial Release.1.1 Corrected some typos, mainly changing intersection to union.1.2 Added terminals for <id> in Problem 3.2 Turn-In ProcedureYour answers to the following questions are to be hand-written neatly or printed on one or more sheets of paper,each with your name in the upper right corner. The homework is to be turned in to my administrative assistant, AndreaWhitesell in 2106 Siebel Center by 9:00am of Wednesday 8 November 2006. Alternately, you may hand it to Prof. ElsaGunter in person before the deadline.3 Objectives and BackgroundThe purpose of this HW is to test your understanding of:• How to use regular expressions and finite state automata to formally express sets of strings (called languages)given by an English language description• How to use Context Free Grammars to formally express languages given by an English language description• How to create datatypes to represent the tokens and parse trees needed to parse strings in the language generatedby a given grammar.• How to disambiguate a grammar.Another purpose of HW3 is to provide you with experience answering non-programming written questions of thekind you may experience on the final.4 Problems1. (20 points) For each of the following languages (ie, sets of strings), write a regular expression generating the set,and draw a finite state automaton accepting the set:1a. (10 points) The set of all strings of a’s and b’s such that every b in each string is immediately preceded by atleast two a’s.b. (10 points) The set of all strings of 0’s, 1’s, and 2’s, such that before each 2 the combined number of 0’s and1’s is always even.2. (27 points) Recall the definition of a regular expression given in class:Given an alphabet Σ of letters, the set of regular expressions over Σ is the smallest set of strings overΣ ∪ {(, ), ∨, ∗, } (where Σ ∩ {(, ), ∨, ∗, } = { }) satisfying the following:• is a regular expression, representing the set containing the empty string.• If a ∈ Σ, then a is a regular expression, representing the set containing the single string containingthe single letter a.• If x is a regular expression, then (x) is a regular expression, representing the same set of strings asx does.• If x and y are regular expressions, then xy is a regular expression, representing the set of all stringsmade from a string from the set represented by x concatenated with a string from the set representedby y.• If x and y are regular expressions, then x ∨ y is a regular expression, representing the union of thesets represented be each of x and y.• If x is a regular expression, then x∗ is a regular expression, representing the set of all strings madefrom concatenating zero or more strings from the set represented by x.a. (12 points) Assuming Σ = {a, b, c}, write a context free grammar over the alphabet Σ ∪ {(, ), ∨, ∗, } thatgenerates all regular expressions.b. (15 points) Using your grammar, draw parse trees for the following regular expressions:(i) (6 points)abc ∗ ∨bac∗(ii) (9 points) (ab(ab) ∗ (ba)ba∗)∗3. (32 points) Consider the following context free grammar:< exp >::=< id >|< exp >< exp >|< exp > ∗ < exp >|< exp > + < exp >| (< exp >)< id >::= a | b | ca. (4 points) Demonstrate that the above grammar is ambiguous.b. (12 point) Rewrite this grammar, introducing new non-terminals as necessary, so that the new grammargenerates the same set of strings as the given, but where application (the second clause) associates to theleft and binds more tightly than ∗, which associates to the right and binds more tightly than +, which alsoassociates to the right.c. (4 points) Write an Ocaml datatype for the tokens of the above language. You may assume the identifiers,<id> take a string argument.d. (12 points) Write a set of Ocaml datatypes to represent the abstract syntax trees corresponding to the parsetrees generated by your grammar.4. (Extra Credit) (20 points) The following is a context free grammar for lambda terms over a given set of identifiers,denoted by <id>:< lambda >::=< id > | < lambda >< lambda > |λ < id > . < lambda > |(< lambda >)Rewrite the grammar so that the new grammar generates the same set of strings as the given grammar, but is notambiguous, and resolves the ambiguities in the manner discussed in class when the lambda calculus was
View Full Document
Unlocking...