CMSC 330, Fall 2006
Organization of Programming Languages
In this project, you will write an OCaml module that can simulate an NFA and can construct an NFA from a regular expression.
What to Submit
You should submit the file nfa.ml.
You can find a p4 directory here that contains an nfa.ml to start from and a .submit file:
Part 1: NFAs in OCaml
In the first part of this project, you will write a series of functions to simulate NFAs using OCaml. We've supplied you with a file nfa.ml that contains the following module signature for NFAs:
module type NFA = sig (* You may NOT change this signature *) (* Abstract type for NFAs *) type nfa (* Type of an NFA transition. (s0, Some c, s1) represents a transition from state s0 to state s1 on character c (s0, None, s1) represents an epsilon transition from s0 to s1 *) type transition = int * char option * int (* Returns a new NFA. make_nfa s fs ts returns an NFA with start state s, final states fs, and transitions ts. *) val make_nfa : int -> int list -> transition list -> nfa (* Takes a step in an NFA. step m ss c returns a list of states that m could be in on seeing input c, starting from any state in ss. There should be no duplicates in the output list of states. If some state n is in the input list, then this function should behave as if any states reachable from n via epsilon transitions are also in the input list. Similarly, if some state n is in the output list, then any states reachable from n via epsilon transitions should also be in the output list. *) val step : nfa -> int list -> char -> int list (* Returns true if the NFA accepts the string, and false otherwise *) val accept : nfa -> string -> bool ... end
Your job is to implement a module Nfa that has this signature. You may not change the NFA signature in any way, though of course your implementation may include more types and functions than are listed in the signature.
Here are descriptions of the elements of this signature, and what you need to do to implement them:
Part 2: Regexps using NFAs
The next part of this project is to implement the regular expression to NFA construction. The signature NFA also contains the following declaractions:
module type NFA = sig (* You may NOT change this signature *) ... type regexp = Empty_String | Char of char | Union of regexp * regexp | Concat of regexp * regexp | Star of regexp (* Given a regular expression, return an nfa that accepts the same language as the regexp *) val regexp_to_nfa : regexp -> nfa end
Here regexp is an OCaml datatype that represents regular expressions:
Your job for this part is to write the function regexp_to_nfa, which takes a regexp and returns an NFA that accepts the same language. You'll want to refer back to the slides from class on this construction.
Hint: You need to be a bit careful whenever you combine NFA representations to be sure that state names (i.e., integers) don't conflict. You might write the following three internal functions as an aid in this process:
The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.
Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.