lip-midterm-2010

This shows you the differences between two versions of the page.

— |
lip-midterm-2010 [2015/10/08 15:20] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | ====== LiP midterm project 2010 ====== | ||

+ | |||

+ | The goal of this project is to specify a simple lexical analyser. | ||

+ | For evaluation purposes, the project is partitioned into five exercises. | ||

+ | |||

+ | == Submission policy == | ||

+ | |||

+ | * You must declare your group by **25.11.2010**. | ||

+ | * The policy for group collaboration is described [[honesty-policy|here]] | ||

+ | * To declare a group, send an email to the [[bart@unica.it|teaching assistant]]. | ||

+ | * The subject of the email must begin with ''[LIP]'' (automatic filtering will be used). | ||

+ | * The body of the email must contain the names of the components (min 1, max 3) | ||

+ | * You must declare your group even though you want to work alone (otherwise I cannot assign you an ID). | ||

+ | * The groups and their IDs will be displayed [[https://spreadsheets.google.com/pub?key=0AinitsakPo0wdHRJaWlMci1NQ2syR0UtY3k2c0VjX3c&hl=en_GB&single=true&gid=2&output=html|here]]. | ||

+ | * You must submit your project by **11.12.2010**, 23.59 GMT +1. | ||

+ | * To submit a project, send it by email to the [[bart@unica.it|teaching assistant]]. | ||

+ | * The subject of the email must be ''[LIP] lip10a-gXX.ml'', where XX is the ID of your group. | ||

+ | * The solutions to the exercises must be pasted into the body of the email (plain text). | ||

+ | * The email will contain no attachments. | ||

+ | * You can submit a project only once. | ||

+ | * You must adhere the LiP [[honesty-policy|honesty policy]]. | ||

+ | * You are not required to exploit the solution of an exercise to solve the subsequent ones: you can start each exercise from scratch. | ||

+ | |||

+ | \\ | ||

+ | |||

+ | ===== Exercise 1 (3 pt) ===== | ||

+ | |||

+ | Consider the type: | ||

+ | <code ocaml> | ||

+ | type 'a partial = None | Some of 'a | ||

+ | </code> | ||

+ | |||

+ | \\ | ||

+ | |||

+ | (a) Write a function ''bind'' with following signature: | ||

+ | <code ocaml> | ||

+ | bind : ('a -> 'b partial) -> 'a -> 'b -> 'a -> 'b partial | ||

+ | </code> | ||

+ | |||

+ | Given a partial function ''f: 'a -> 'b partial'', an identifier ''x: 'a'' and a value ''v: 'b'', | ||

+ | the expression ''bind f x v'' will evaluate to a function ''g: 'a -> 'b partial'' such that, | ||

+ | for all identifiers y: | ||

+ | * if y=x, then g y = Some v | ||

+ | * if y≠x, then g y = f y | ||

+ | |||

+ | \\ | ||

+ | |||

+ | (b) Write a function ''join'' with following signature: | ||

+ | <code ocaml> | ||

+ | join : ('a -> 'b partial) -> ('a -> 'b partial) -> 'a -> 'b partial | ||

+ | </code> | ||

+ | |||

+ | Given two partial functions ''f'',''g'' with type '''a -> 'b partial'', | ||

+ | the expression ''join f g'' will evaluate to a function ''h'' with type '''a -> 'b partial'' | ||

+ | such that: | ||

+ | * h x = f x = g x, if both f and g are defined on x, and f x = g x | ||

+ | * h x = f x, if g is undefined on x | ||

+ | * h x = g x, if f is undefined on x | ||

+ | * h x = None, if neither f nor g are defined on x | ||

+ | |||

+ | Applying the function ''h'' on some ''x'' for which both f and g are defined on ''x'', and ''f x ≠ g x'', | ||

+ | will result in an exception. | ||

+ | |||

+ | \\ | ||

+ | |||

+ | |||

+ | ===== Exercise 2 (6 pt) ===== | ||

+ | |||

+ | Define datatype for specifying sets. A set is an unordered collection of elements, without repetitions. | ||

+ | A set of elements of type '''a'' will be implemented as a list of type '''a list''. | ||

+ | The following functions will be provided: | ||

+ | |||

+ | * ''member : 'a -> 'a set -> bool''. The expression ''member x s'' will evaluate to ''true'' iff the element ''x'' belong to ''s''. | ||

+ | * ''isempty : 'a set -> bool''. The expression ''isempty s'' will evaluate to ''true'' iff the set ''s'' is empty. | ||

+ | * ''union : 'a set -> 'a set -> 'a set''. The expression ''union s0 s1'' will evaluate to the union of the sets ''s0'' and ''s1''. | ||

+ | * ''intersect : 'a set -> 'a set -> 'a set''. The expression ''intersect s0 s1'' will evaluate to the intersection of the sets ''s0'' and ''s1''. | ||

+ | * ''setminus : 'a set -> 'a set -> 'a set''. The expression ''setminus s0 s1'' will evaluate to the difference between the sets ''s0'' and ''s1''. | ||

+ | * ''setenum : 'a list -> 'a set''. The expression ''setenum l'' will evaluate to a set that contains all (and only) the elements of the list ''l''. | ||

+ | * ''setcomp : 'a set -> ('a -> bool) -> 'a set''. The expression ''setcomp s p'' will evaluate to the largest subset ''s''' of ''s'' such that the predicate ''p'' is true for all the elements of ''s'''. | ||

+ | * ''subset: 'a set -> 'a set -> bool''. The expression ''subset s0 s1'' will evaluate to true iff ''s0'' is a proper subset of ''s1''. | ||

+ | * ''powset: 'a set -> 'a set set''. The expression ''powset s'' will evaluate to the set of all the possible subsets of ''s''. | ||

+ | \\ | ||

+ | |||

+ | |||

+ | ===== Exercise 3 (6 pt) ===== | ||

+ | |||

+ | (a) Define a datatype for specifying Deterministic Finite State Automata (DFAs). | ||

+ | |||

+ | (b) Define a function ''step'' that, given a DFA ''a'', a state ''q'' and an input symbol ''s'', | ||

+ | evaluates the next state of ''a'' upon reading ''s'' on state ''q''. | ||

+ | |||

+ | %%(c)%% Define a function ''recognize'' such that | ||

+ | the expression ''recognize a l'' | ||

+ | evaluates to true iff the DFA ''a'' accepts the sequence of input symbols ''l''. | ||

+ | |||

+ | (d) Write a DFA that recognizes the language (a|b)*abb (on the alphabet {a,b}). | ||

+ | Use the function ''recognize'' to test if it accepts the sequences abbabb and bababba. | ||

+ | |||

+ | \\ | ||

+ | |||

+ | |||

+ | ===== Exercise 4 (12 pt) ===== | ||

+ | |||

+ | (a) Define a datatype for specifying Nondeterministic Finite State Automata (NFAs). | ||

+ | |||

+ | (b) Write a function ''dfa_of_nfa'' that transforma a NFA into a DFA which accepts the same language. | ||

+ | The function will use the subset construction algorithm ((J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata Theory, Languages, and Computation. Prentice Hall, 2007.)). | ||

+ | |||

+ | %%(c)%% Write an NFA that recognizes the language (a|b)<sup>*</sup>abb (on the alphabet {a,b}). Use the function ''dfa_of_nfa'' to transform it into a DFA. | ||

+ | |||

+ | \\ | ||

+ | |||

+ | |||

+ | ===== Exercise 5 (10 pt) ===== | ||

+ | |||

+ | (a) Define a datatype for specifying regular expressions. | ||

+ | |||

+ | (b) Write a function ''nfa_of_regexp'' that transforms a regular expression into a NFA | ||

+ | which accepts the same language. | ||

+ | The function will use the Thompson's algorithm ((J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata Theory, Languages, and Computation. Prentice Hall, 2007.)). | ||

+ | |||

+ | %%(c)%% Using the datatype defined at item (a), write a regular expression for (a|b)<sup>*</sup>abb. Use the function ''nfa_of_regexp'' to construct an NFA that | ||

+ | recognizes the same language. | ||

+ | |||

+ | \\ | ||

lip-midterm-2010.txt · Last modified: 2015/10/08 15:20 (external edit)