Skip to content
Pull requests
Issues
Marketplace
Explore
Learn Git and GitHub without any code!
Using the Hello World guide, youll start a branch, write comments, and open a pull request.
Read the guide
Watch 12
Star 17
Fork 44
anwarmamatcmsc330fall19public
Code
Issues 0
Pull requests 0
Projects 0
Wiki
Security
Insights
Branch: master
Create new file
Upload files
Find file
History
cmsc330fall19publicproject3
pavanravindra added intersection to Sets module documentation
Latest commit
091a6dd
19 hours ago
Type
Name
Latest commit message
Commit time
..
bin
updated project 3
13 days ago
depsets
added intersection to Sets module documentation
19 hours ago
dep4.07.1sets
updated project 3
13 days ago
images
Added Project 3
15 days ago
src
updated project 3
13 days ago
test
updated project 3
13 days ago
.submit
updated project 3
13 days ago
README.md
Update README.md
3 days ago
duneproject
Added Project 3
15 days ago
duneworkspace
Added Project 3
15 days ago
ocamlversion.sh
updated project 3
13 days ago
submit.jar
Added Project 3
15 days ago
test.sh
updated project 3
13 days ago
utop.sh
updated project 3
13 days ago
viz.sh
updated project 3
13 days ago
README.md
Project 3: Regular Expression Engine
Due: October 21 Late October 22 at 11:59:59 PM
Points: 35P35R30S
Overview
In this project you will implement algorithms to work with NFAs, DFAs, and regular expressions. In particular, you will implement an accept function to see whether a string is matched by a NFA; you will write a nfatodfa function to convert an NFA to a DFA using the subset construction; and you will write a regextonfa function to convert a regular expression to an NFA. You will also implement several other helper functions to assist in these tasks.
The project is broken into three parts: algorithms on NFAs; converting a DFA to an NFA; and convertingworking with Regular Expressions. NFAs and DFAs are implemented in srcnfa.ml, and regexes in srcregex.ml.
In class we implemented a Regular Expression Interpreter through a series of reductions. First convert the RegExp to an NFA, then the NFA to a DFA, and then run the DFA on an input string to see if the string is accepted. This project will not follow that sequence exactly, but will allow you to work with the reductions so you understand each step in the sequence.
Heres how the parts can be assembled into an Interpreter. In Part I youll simulate an NFA. You can do that directly, or you can use Part II to convert to a DFA and then assume you have a DFA to simulate. In Part II youll implement an NFA to DFA converter. In Part III youll convert a RegExp to an NFA. You can put these parts together to create an Interpreter: Input a RegExp to Part III to create an NFA, and then input that NFA and a string to Part I to simulate the resulting NFA. Or, input that NFA to Part II to get a DFA, then since the class of DFAs is a subset of NFAs, input that DFA to Part I to simulate it. You arent required to create these workflows, as well test each part independently, but you can experiment with them. Note that the same Ocaml type, nfat, is used for both NFAs and DFAs in this project, so the function to convert an NFA to a DFA takes an nfat to an nfat.
Ground Rules
To begin this project, you will need to commit any uncommitted changes to your local branch and pull updates from the git repository. Click here for directions on working with the Git repository.
This is NOT a pair project. You must work on this project alone as with most other CS projects. See the Academic Integrity section for more information. In your code, you may use any nonimperative standard library functions with the exception of printing, see below, but the ones that will be useful to you will be found in the Pervasives, List and String modules. The only imperative feature you may use is the provided fresh function in Part 3. You will receive a 0 for any functions using restricted featureswe will be checking your code!
Several helper functions have been provided for you, as detailed at the end of this document. We have also provided a Sets module that correctly implements the functions for a functional Set module. Note: the functions in the Sets module assume that the inputs are valid sets i.e., they do not contain duplicates. They will have undefined behavior if you try to give them inputs that do not meet this requirement such as 1; 2; 2; 3.
Testing
The procedure for testing this project is the same as the previous project. dune handles the majority of the work but, an environment variable must be set for dune to know where to find the precompiled binary files distributed with the project.
Public and student tests can be run using the same dune command that you used in the previous projects but, you need to set the environment variable OCAMLPATH before running the command. The exact value of OCAMLPATH will depend on the version of OCaml you are using. If you have version 4.07.0, you can use the following commands verbatim but, if you have 4.07.1 you will need to replace all instances of dep with dep4.07.1. The full command is now env OCAMLPATHdep dune runtest f. Setting OCAMLPATH tells dune where it can find the functions over sets that we have provided. You will need to provide this environment variable for every dune command so you may want to add it to your environment once by running OCAMLPATHdep as separate command before using dune. We have also provided a shell script test.sh that runs the command given above. To run this, type sh test.sh at a terminal.
For testing your regular expressions and nfatodfa, weve provided another build target: viz. When you run this command, it will read a regular expression from standard in, compose an NFA from it, and export that NFA to Graphviz before rendering to a PNG. For this target to work, however, you must install Graphviz.
You are not required to do this, but it may be helpful in debugging your code. Once youve performed these steps, you can run the visualizer as follows:
1.Run the shell script .viz.sh or the command env OCAMLPATHdep dune exec binviz.bc to open the input shell.
2.The shell will ask for a regular expression. Type without spaces and using only the constructs supported by this project.
3.Select if you want to convert the NFA to a DFA with your conversion function before visualizing.
4.You should be notified that the image has been successfully generated and put in output.png.
5.Use an image viewer of choice to open output.png and see the visual representation of your generated NFA.
Part 1: NFAs
This first part of the project asks you to implement some functions for working with NFAs. In particular, you will be asked to implement the move and epsilon closure functions described in class; these will be handy for Part 2. You will also implement an accept function to determine whether a string is matched by a given NFA; both move and epsilon closure may be handy here, too.
NFA Types
Before starting, youll want to familiarize yourself with the types you will be working with.
The type nfat is the type representing NFAs. It is modeled after the formal definition of an NFA, a 5tuple , Q, q0, F,where:
1. is a finite alphabet,
2.Q is a finite set of states,
3.q0Q is the start state,
4.FQ is the set of accept states, and
5. : QPQ is the transition function.
We translate this definition into OCaml in a straightforward way using record syntax:
type q, s transitionqs optionq
type q, s nfat
sigma : s list;
qs : q list;
q0 : q;
fs : q list;
delta : q, s transition list;
Notice the types are parametric in state q and symbol s.
The type transition represents NFA transitions. For example:
let t10, Some c, 1Transition from state 0 to state 1 on character c
let t21, None, 0Transition from state 1 to state 0 on epsilon
An example NFA would be:
let nfaex
sigmaa;
qs0; 1; 2;
q00;
fs2;
delta0, Some a, 1; 1, None, 2
This looks like:
Here is a DFA:
let dfaex
sigmaa; b; c;
qs0; 1; 2;
q00;
fs2;
delta0, Some a, 1; 1, Some b, 0; 1, Some c, 2
This looks like:
Functions
Here are the functions you must implement:
move nfa qs s
Type: q, s nfatq lists optionq list
Description: This function takes as input an NFA, a list of initial states, and a symbol option. The output will be a list of states in any order, with no duplicates that the NFA might be in after making one transition on the symbol or epsilon if None, starting from one of the initial states given as an argument to move. If c is not in the alphabet sigma, then return the empty list.
Examples:
move nfaex 0 Some a1nfaex is the NFA defined above
move nfaex 1 Some a
move nfaex 2 Some a
move nfaex 0;1 Some a 1
move nfaex 1 None2
Explanation:
i.Move on nfaex from 0 with Some a returns 1 since from 0 to 1 there is a transition with character a.
ii.Move on nfaex from 1 with Some a returnssince from 1 there is no transition with character a.
iii.Move on nfaex from 2 with Some a returnssince from 2 there is no transition with character a.
iv.Move on nfaex from 0 and 1 with Some a returns 1 since from 0 to 1 there is a transition with character a but from 1 there was no transition with character a.
v.Notice that the NFA uses an implicit dead state. If s is a state in the input list and there are no transitions from s on the input character, then all that happens is that no states are added to the output list for s.
vi.Move on nfaex from 1 with None returns 2 since from 1 to 2 there is an epsilon transition.
eclosure nfa qs
Type: q, s nfatq listq list
Description: This function takes as input an NFA and a list of states. The output will be a list of states in any order, with no duplicates that the NFA might be in making zero or more epsilon transitions, starting from the list of initial states given as an argument to eclosure. You can assume you will always be passed in a state that is in nfas states list.
Examples:
eclosure nfaex 00
eclosure nfaex 11;2
eclosure nfaex 2 2
eclosure nfaex 0;10;1;2
Explanation:
i.eclosure on nfaex from 0 returns 0 since there is no where to go from 0 on an epsilon transition.
ii.eclosure on nfaex from 1 returns 1;2 since from 1 you can get to 2 on an epsilon transition.
iii.eclosure on nfaex from 2 returns 2 since there is no where to go from 2 on an epsilon transition.
iv.eclosure on nfaex from 0 and 1 returns 0;1;2 since from 0 you can only get to yourself and from 1 you can get to 2 on an epsilon transition but from 2 you cant go anywhere.
accept nfa s
Type: q, char nfatstringbool
Description: This function takes an NFA and a string, and returns true if the NFA accepts the string, and false otherwise. You will find the functions in the String module to be helpful. You might find it useful to use nfatodfa, implemented in Part 2 below, as part of your accept implementation, but this is not required.
Examples:
accept dfaex false dfaex is the NFA defined above
accept dfaex actrue
accept dfaex abcfalse
accept dfaex abactrue
Explanation:
i.accept on dfaex with the stringreturns false because initially we are at our start state 0 and there are no characters to exhaust and we are not in a final state.
ii.accept on dfaex with the string ac returns true because from 0 to 1 there is an a transition and from 1 to 2 there is a c transition and now that the string is empty and we are in a final state thus the nfa accepts ac.
iii.accept on dfaex with the string abc returns false because from 0 to 1 there is an a transition but then to use the b we go back from 1 to 0 and we are stuck because we need a c transition yet there is only an a transition. Since we are not in a final state thus the function returns false.
iv.accept on dfaex with the string abac returns true because from 0 to 1 there is an a transition but then to use the b we go back from 1 to 0 and then we take an a transition to go to state 1 again and then finally from 1 to 2 we exhaust our last character c to make it to our final state. Since we are in a final state thus the nfa accepts abac.
Part 2: DFAs
In this part, our goal is to implement the nfatodfa function. It uses the subset construction to convert an NFA to a DFA. For help with understanding Subset Construction you can look at the lecture notes and here. We recommend you implement the move and eclosure parts of Part 1 before starting Part 2, since they are used in the subset construction.
Remember that every DFA is also an NFA, but not the other way around. Recall that the subset construction converts an NFA to a DFA by grouping together multiple NFA states into a single DFA state. Hence, our DFA type is q list, s nfat. Notice that our states are now lists representing sets of states from the NFA.
To write nfatodfa we will write some helpers. These helpers follow the NFA to DFA conversion method discussed in lecture. We will test these functions individually in the public tests to help you track your progress and find bugs. Remember, you can always add more student tests in teststudent.ml! Hint: newstates, newtrans, and newfinals can all be implemented in one line!
newstates nfa qs
Type: q, s nfatq listq list list
Description: Given an NFA and a list of states from that NFA a single state in the DFA computes all the DFA states that you can get to from a transition out of qs including the dead state. You can return the list in any order, with or without duplicates. Dead states are represented by empty lists. Note: each element in the list corresponds to all of the states you can get to from one character of the alphabet sigma followed by any number of epsilon transitions
Examples:
newstates nfaex 01; 2
newstates dfaex 0; 11; 0; 2
newtrans nfa qs
Type: q, s nfatq listq list, s transition list
Description: Given an NFA and a list of states from that NFA a single state in the DFA computes all the transitions coming from qs including the dead state in the DFA.
Examples:
newtrans dfaex 0; 10; 1, Some a, 1; 0; 1, Some b, 0; 0; 1, Some c, 2
newfinals nfa qs
Type: q, s nfatq listq list list
Description: Given an NFA and a list of states from that NFA a single state in the DFA returns qs if qs is final in the DFA andotherwise.
Examples:
newfinals dfaex 0; 1; 20; 1; 2
newfinals dfaex 0; 1
nfatodfa nfa
Type: q, s nfatq list, s nfat
Description: This function takes as input an NFA and converts it to an equivalent DFA. The language recognized by an NFA is invariant under nfatodfa. In other words, for all NFAs nfa and for all strings s, accept nfa saccept nfatodfa nfa s.
Suggestion
The nfatodfa algorithm is pretty substantial. While you are free to design it in whatever manner you like referring the lecture slides and notes for assistance, we suggest you consider writing a helper function nfatodfastep that does most of the work. This function is invoked for each iteration of the algorithm. Here is its description:
nfatodfastep nfa dfa wrk
Type: q, s nfatq list, s nfatq list listq list, s nfat
Description: First, lets take a look at what is being passed into the function for clarity:Parameters
nfa: the NFA to be converted into a DFA.
dfa: the DFA to be created from the NFA. This will act as the accumulator in the function. Each time this function is called, the DFA should be updated based on the worklist.
wrk: a list of unvisited states.
Given an NFA, a partial DFA, and a worklist, this function will compute one step of the subset construction algorithm. This means that we take an unvisited DFA state from the worklist and add it to our DFA that we are creating updating the list of all states, transitions, and final states appropriately. Our worklist is then updated for the next iteration by removing the newly processed state. You will want to use the previous three functions as helpers. They can be used to update the DFAs states, transistions, and final states.
Once again, you are free to skip implementing this function if you feel you have a better approach.
Part 3: Regular Expressions
For the last part of the project, you will implement code to convert a regular expression in the format given below to an NFA. Then you could use your NFA module developed above to match particular strings. The Regexp module represents a regular expression with the type regexpt:
type regexpt
EmptyString
Char of char
Union of regexpregexp
Concat of regexpregexp
Star of regexp
This datatype represents regular expressions as follows:
EmptyString represents the regular expression recognizing the empty string not the empty set!. Written as a formal regular expression, this would be epsilon.
Char c represents the regular expression that accepts the single character c. Written as a formal regular expression, this would be c.
Union r1, r2 represents the regular expression that is the union of r1 and r2. For example, UnionChar a, Charb is the same as the formal regular expression ab.
Concat r1, r2 represents the concatenation of r1 followed by r2. For example, ConcatChar a, Char b is the same as the formal regular expresion ab.
Star r represents the Kleene closure of regular expression r. For example, Star Union Char a, Char b is the same as the formal regular expression ab.
Here is the function you must implement:
regexptonfa regexp
Type: regexptnfat
Description: This function takes a regexp and returns an NFA that accepts the same language as the regular expression. Notice that as long as your NFA accepts the correct language, the structure of the NFA does not matter since the NFA produced will only be tested to see which strings it accepts. Remember, EmptyString represents the regular expression recognizing epsilon, as stated above.
Provided Functions
The rest of these functions are implemented for you as helpers. Use them as you like; you dont have to modify them.
explode s
Type: stringchar list
Description: This function takes a string and converts it into a character list. The following function may be helpful when writing accept in Part 1.
fresh
Type: unitint
Description: This function takes in type unit as an argument similar to Null. This function uses imperative OCaml to return an int value that has not been used before by using a reference to a counter. You might find this helpful for implementing regexptonfa.
Examples:
fresh1
fresh2
fresh3
The next two functions rely on your code for correctness!
stringtonfa s
Type: stringnfa
Description: This function takes a string for a regular expression, parses the string, converts it into a regexp, and transforms it to an nfa, using your regexptonfa function. As such, for this function to work, your regexptonfa function must be working. In the starter files we have provided function stringtoregexp that parses strings into regexp values, described next.
stringtoregexp s provided for you
Type: stringregexp
Description: This function takes a string for a regular expression, parses the string, and outputs its equivalent regexp. If the parser determines that the regular expression has illegal syntax, it will raise an IllegalExpression exception.
Examples:
stringtoregexp aChar a
stringtoregexp abUnion Char a, Char b
stringtoregexp abConcatChar a,Char b
stringtoregexp aabConcatChar a,ConcatChar a,Char b
stringtoregexp aEStarUnionChar a,EmptyString
stringtoregexp aEabConcatStarUnionChar a,EmptyString,UnionChar a,Char b
In a call to stringtoregexp s the string s may contain only parentheses, , , az lowercase, and E for epsilon. A grammatically illformed string will result in IllegalExpression being thrown. Note that the precedence for regular expression operators is as follows, from highest1 to lowest4:
Precedence
Operator
Description
1
parentheses
2
closure
3
concatenation
4
union
Also, note that all the binary operators are right associative.
Project Submission
You should submit the files nfa.ml and regexp.ml containing your solution. You may submit other files, but they will be ignored during grading. We will run your solution as individual OUnit tests just as in the provided public test file.
If you submit your entire directory ENSURE you do dune clean before submitting or it will not compile
Be sure to follow the project description exactly! Your solution will be graded automatically, so any deviation from the specification will result in lost points.
You can submit your project in two ways:
Submit your files directly to the submit server by clicking on the submit link in the column next to the project number. Then, use the submit dialog to submit all your files. Select your file using the Browse button, then press the Submit project! button. You do not need to put it in a zip file.
Submit directly by executing the submission script on a computer with Java and network access. Included in this project are the submission script and related files listed under Project Files. These files should be in the directory containing your project. From there you can run the command java jar submit.jar. Make sure that your submission is received by checking the submit server after submitting.
Academic Integrity
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, which you should review before starting.
2019 GitHub, Inc.
Terms
Privacy
Security
Status
Help
Contact GitHub
Pricing
API
Training
Blog
About
Reviews
There are no reviews yet.