cps721: Assignment 4 (100 points).
Due date: Electronic file – before Monday, November 15, 2021, 17:00. Read last page. You must work in groups of TWO, or THREE. You should not work alone.
YOU SHOULD NOT USE “;” (disjunction) “!” (cut) AND “−>” IN YOUR PROLOG PROGRAMS.
You can discuss this assignment only with your CPS721 group partners or with CPS721 instructor. By submitting this assignment you acknowledge that you read and understood the course Policy on Collabo- ration in homework assignments stated in CPS721 course management form.
Copyright By PowCoder代写 加微信 powcoder
This assignment will exercise what you have learned about natural language processing. In this assignment, we imagine a computerized travel assistant. Ultimately, we would like to be able to tell our assistant what to do using ordinary English imperative sentences like “Book me on the next Air Canada flight from Toronto to Montreal.” As in class, to interpret English sentences like these, we need to construct a database of facts about our world, a lexicon, and a parser/interpreter. As in class, we will restrict our attention here to the English noun phrases like “a West Jet flight from Toronto”.
1. Before we start using any English words, build in Prolog a simple database of facts (e.g., about 10-15 facts of each type) with the following predicates:
• flight(F,C,X,Y ) where F is a name of a flight, C is a carrier, and X and Y are the from and to cities, e.g.: flight(aa300,americanAirlines,ny,austin). flight(ua95,unitedAirlines,chicago,toronto). flight(ac987,airCanada,edmonton,montreal). flight(ac087,airCanada,vancouver,shanghai).
For simplicity, we assume that each flight number is associated with the unique company serving this flight, e.g.: ac987 is served only by airCanada. Every flight must have a departure and arrival times in your KB.
• dtime(F light, City, T ime): The departure time of F light from City is T ime, e.g., dtime(ac987,edmonton,1130). dtime(aa300,ny,1200). /* ny stands for */
dtime(ua95,chicago,1215). dtime(ac087,vancouver,1300).
• atime(F light, City, T ime): The arrival time of F light to City is T ime, e.g.: atime(ac987,montreal,1645). atime(ua95,toronto,1330).
atime(aa300,austin,1600). atime(ac087,shanghai,2300).
• location(X,C), where X is a city, and C is a country. For example: location(toronto,canada). location(shanghai,china).
We shall make some simplifying assumptions. First, all flights have the same daily schedule, seven days per week. That’s why we do not have predicates like
dtime(Flight,City,DayOfWeek,Time), or atime(Flight,City,DayOfWeek,Time). Second, all flights begin and terminate within the same day. This means that there are no over-night flights which depart in the evening, and arrive at their destination during the morning of the following day. Third, there are no time zones, so if it is now 1435 in Toronto, it is also 1435 in Vancouver. This means we use some kind of universal time. Finally, understand time 1546 as abbreviation for 15h46min. Hence, subtraction/addition has to be done modulo 60.
Keep your database in the file travel.pl The facts included in your database can be imaginary; make it up so that most queries will get positive answers and will retrieve some data from your data base. Show that your database works properly by formulating the following queries in Prolog (similar to what you did in the first assignment), and obtaining suitable answers:
(a) Is there a flight from Toronto to a Canadian city? If yes, retrieve all of them one-by-one.
(b) How much time it takes for Air Canada to fly to Los Angeles? (i.e., is there a flight served by Air Canada? If yes, how much time it takes?)
(c) What is departure time of the United Airlines flight from Chicago to Toronto?
(d) Is there an international flight not from Montreal to a city in UK? (Note: for purposes of this assignment, a flight
is domestic if it is between two cities in the same country, and international otherwise.)
(e) Is there an Air Canada domestic flight leaving Edmonton?
(f) What international flight leaves from Toronto and how much time it takes?
(g) How much time takes flying from Toronto to Shanghai in case if there is one intermediate stop in Vancouver, each leg has its own flight number, and both legs are served by the same company?
(h) Is there an international flight leaving Montreal between 6am and 9am and arriving in USA before 4pm?
(i) What is the shortest flight to China from Toronto? (We understand shortest as taking the minimal time. Also, the flight that takes time longer than time taken by another flight between same two cities is called below a long flight.)
(j) Is there a morning flight from Canada to that arrives there before 1pm? (We interpret morning as any time between 5am and 9am, and assume that a morning flight is a flight that departs in the morning. Similarly, day flights are flights that depart from 9am to noon, afternoon flights depart from noon to 5pm, and evening flights depart from 5p to 10pm. You can assume that no flights depart between 10pm and 5am.)
(k) Are there more than 2 different cities in Canada that can be destinations of flights departing from Toronto before noon?
(l) What are the two different cities in China that are destinations of flights from Canada?
(These queries should not use English noun phrases!) You can use more queries, but implement at least all the 12 queries mentioned above. It is up to you to formulate a range of queries that demonstrates that your database is designed properly (each flight has an arrival and a departure time, and so on). Keep your queries and answers computed by Prolog in the file travel.txt
Once you have this working, you are ready to consider English noun phrases and the flights they refer to. Here are some examples of the kinds of queries your system should be able to answer:
1. what([a,morning,flight,from,canada,to,an,american,city],F).
2. what([an,afternoon,airCanada,flight,from,toronto,to,losAngeles],F).
(note: for simplicity, we use “airCanada” or “losAngeles” as if they were single English words.)
3. what([a,day,international,flight,to,a,city,in,uk],F).
4. what([a,morning,domestic,flight,from,toronto,with,any,afternoon,arrival,time],F).
5. what([a,unitedAirlines,international,flight,from,a,city,in,canada],F).
6. what([any,international,afternoon,flight,between,a,city,in,canada,and, an,american,city],FN).
7. what([a,long,day,international,flight,from,toronto,to,uk,with,any, evening,arrival,time],F).
8. what([the,shortest,flight,between,a,canadian,city,and,a,chinese,city],F).
9. what([any,afternoon,arrival,time,of,a,day,domestic,flight,to,an,american,city],T).
10. what([a,day,departure,time,of,a,domestic,flight,to,miami],T).
11. what([the,shortest,flight,from,toronto,with,any,morning,departure,time,to, a,canadian,city],F).
12. what([the, day, flight, from, edmonton, to, montreal], FN).
2. Build a lexicon, as we did in class, of articles, adjectives, proper nouns, common nouns, and prepositions. To cover the above examples, you will need at least these words:
articles: a, an
common nouns: flight, city, country, time …
prepositions: to, from, in, with, …
proper nouns: toronto, losAngeles, england, montreal, canada, shanghai, miami… adjectives: domestic, international, airCanada, unitedAirlines, long, shortest,
arrival,departure,morning,day,afternoon,evening,canadian, chinese, …
(Actually, “Air Canada” is not really an adjective, but more a brand name like “Roots” or “Colgate”. However, it is close enough to an adjective.) Recall that a flight from X to Y is considered long, if it takes time longer than the time taken by another flight from X to Y . You should not introduce any new atomic statements, i.e., your atomic statements can use only the 4 predicates mentioned above in Part 1. Your lexicon should include all the words mentioned above (in total, 20 words or more, apart from articles and proper nouns). The word “any” should be treated as an article. Notice that some words are ambiguous, and for this reason, you need several rules for them in your lexicon: one rule per possible meaning. (For comparison, consider the 4 rules for the preposition “with” discussed in class.) Remember that it is easy to defeat a language understanding program by using a word that it does not know about. Vocabulary is important in these systems. Make yours as smart as you can. Three (3) best Prolog programs that will do significatly more work than specified explicitly in this assignment will get bonus marks (e.g., implement 10 or more additional common noun and adjectives, or use in your lexicon nouns, prepositions and adjectives from the language other than English). Bonus marks will be given at the discretion of the TA: minor variations will not be awarded any extra marks. Demonstrate your creativity to get bonus marks!
3. Copy the noun phrase parser/interpreter given in class (or write your own), and define the what predicate used above. The parser must be also in the same file travel.pl
4. Test the what predicate on a variety of noun phrases, like those above, showing that it is capable of identifying the entities being referred to by your noun phrases. It is up to you to choose noun phrases for testing, but you must convincingly demonstrate that your program works properly. Try at least 10 new different noun phrases (in addition to the phrases given to you). Remember that testing your program is very important part of the software development cycle. You lose marks if you do not test your program as required. Copy all results of your tests into travel.txt Include there all your observations about the program, and if you like, make suggestions whether an approach needs improvements to answer correctly queries that use noun phrases.
5. Do not attempt this work until the previous parts of your assignment are complete. The English noun phrases described above are quite limited. Generalize your program to handle some additional features of English:
• Handle the article “the” properly. The trick here is that a noun phrase like “the Air Canada flight from Montreal to Toronto” should succeed in naming a flight if there is a unique flight of the appropriate kind. Similarly, “the shortest flight from Toronto to China” should retrieve the unique (direct) flight that takes minimal time. Test your implementation with queries and show your program works correctly.
• Handle prepositional phrases of the form “between X and Y ” as in “a flight between Vancouver and a city in Korea”, or as in “a flight between Canada and USA”. Query your program to show it works correctly.
Handing in solutions:
(a) An electronic copy of your database, lexicon, and parser in one file travel.pl must be included in your zip archive; (b) a copy of your session(s) with Prolog, showing the queries you submitted and the answers returned: name this file travel.txt and include it in your zip archive. It is up to you to formulate a range of queries that demonstrate that your program is working properly; you must try all queries mentioned above.
How to submit this assignment. Read regularly Frequently Answered Questions and replies to them that are linked from the Assignments Web page at
http://www.scs.ryerson.ca/ ̃mes/courses/cps721/assignments.html
If you write your code on a Windows machine, make sure you save your files as plain text that one can easily read on Linux machines. Before you submit your Prolog code electronically make sure that your files do not contain any extra binary symbols: it should be possible to load travel.pl into a recent release of ECLiPSe Prolog (tkECLiPSe on moon), compile your program and ask testing queries. TA will mark your assignment using ECLiPSe Prolog. If you run any other version of Prolog on your home computer, it is your responsibility to make sure that your program will run on ECLiPSe Prolog (release 6 or any more recent release), as required. For example, you can run a command-line version of ECLiPSe on moon remotely from your home computer to test your program (read handout about running ECLiPSe Prolog). To submit files electronically do the following. First, create a zip archive on any moon Linux server:
zip yourLoginName.zip travel.pl travel.txt
where yourLoginName is the login name of the person who submits this assignment from a group. Remember to mention at the beginning of each file student numbers and names of all people who participated in discussions (see the course management form). You may be penalized for not doing so.
Second, upload your ZIP file yourLoginName.zip
to D2L into “Assignment 4” folder. Make sure it includes all your files. Improperly submitted assignments will not be marked. In particular, you are not allowed to submit your assignment by email to a TA or to the instructor.
Revisions: If you would like to upload a revised copy of your assignment, then simply upload it again. (The same person must upload.) A new copy of your assignment will override the old copy. You can upload new versions as many times as you like and you do not need to inform anyone about this. Do not ask your team members to upload your assignment, because TA will be confused which version to mark: only one person from a group should submit different revisions of the assignment. The groups that submit more than one copy of their solutions will be penalized. The time stamp of the last file you upload will determine whether you have submitted your work on time.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com