COMP90049 Knowledge Technologies (Semester 1, 2012) Workshop exercises: Week 2
1. Identify some tasks which fall under the purview of “knowledge technologies.” Contrast these with tasks that are “concrete tasks” or those that are typically considering to be in the domain of “artificial intelligence.” • Refer to lecture notes 2. What is “knowledge discovery?” Describe a process through which we might be able to answer the question “Where shall we go for dinner tonight?” using Google (http://www.google.com) as a resource. Identify the various instances of “data,” “information,” and “knowledge” encountered in your system. Why are the following poor answers (and why might they be proposed by your system)? (a) “Jeremy Nicholson’s house” • No way! (b) “Djon’s Steak and Lobster House” • Melbourne, FL, USA (c) “maze” • Closed in August 2011 3. What are “structured data” and “unstructured data?” Give examples of each, and indicate how you would handle them in a formal (computational) setting. What would “semi-structured data” be? Are any of the examples you gave actually instances of semi-structured data? In what ways is it easier or more challenging to handle semi-structured data? • Structured data: corresponds to a schema, Unstructured data: no schema • Semi-structured data: a schema exists (or could exist; consider grammar of the English language) which enforces structure (or partial structure), but some information remains inaccessible/unstructured anyway 4. Revise the following regular expression operators: ( ) [ ] { } . * + ? ^ $ | \ For each of the following, give a couple of examples of strings which the regular expression pattern will match. Describe (colloquially) the set of strings that the pattern is designed to match. (a) [a-zA-Z]+ • One or more letters of the Latin alphabet, e.g. a1PH@BeT (b) ^[A-Za-z][a-z]*$ • A string starting with 1 uppercase or lowercase letter (of the Latin alphabet), follwed by any number of lowercase letters (only), e.g. Alphabet (c) p[aeiou]{,2}t • Up to two vowels between the letters ‘p’ and ‘t’, e.g. pt, pout, carpet (d) \s(\w+)\s\1 • A whitespace character followed by any number of alphanumeric (“word”) characters (and defined as the first group), followed by another whitespace character (potentially different than the first), followed by a copy of the first group, e.g. test testing (e) ([0-9A-Fa-f]{2}:){2}[0-9A-Fa-f] 1

• Two pairs of hexadecimal digits separated by colons, followed by a single hex digit (MAC address fragment) (f) ^(\+[0-9][0-9]|0)[0-9] ([0-9][ -]?){8}$ • An Australian (8 digit) telephone number with optional separators and either region or country code, e.g. +613 8344 1363, 03 83-4413-63 5. Write a regular expression to solve the following problems: (a) Match a number in scientific E notation, e.g. 2.00600e+003 • /^\d(\.\d+)?e(\+|-)?\d+$/ (b) Match a price • /^\$\d+(\.\d{1,2})?$/ (c) Remove HTML comments • From http://ostermiller.org/findhtmlcomment.html: s/\// (d) Find long words whose letters are in alphabetical order • Note that “long” is too vague for us to formalise. For discussion purposes, let us consider “long” to mean of length at least 10 characters. There is no regular language which describes the set of strings that are both at least 10 characters long, and have all their letters in ascending order. The proof of this is left as an exercice to the reader. We offer an implementation that utilises lookahead assertions:

/^(?=.{10,})a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$/ (e) Validate an email address • Note that an email address can be a tricky thing to define. See http://www.ex-parrot.com/
~pdw/Mail-RFC822-Address.html for a perl regular expression that validates address according to the RFC 822 grammar. See a relevant discussion at http://stackoverflow.com/questions/ 201323/what-is-the-best-regular-expression-for-validating-email-addresses. Our example solution (although flawed), is taken from there.

/^(\w|-)+(\.(\w|-)+)*@(\w|-)+(\.(\w|-)+)*(\.[a-z]{2,4})$ (f) Find all of the word mnemonics that map on to all possible level-9 Computer Science subject codes (90001,90002,...,90099) based on the standard telephone keypad mapping (where 2 maps on to A/B/C, 3 maps on to D/E/F, etc.) • ^[W-Z] [A-Z ][A-Z]$ 6. [EXTENSION] Practice using awk, or alternatively, bash-scripting with grep and sed. For example, write a program that finds all of the email addresses in enron-headers.txt. (You might contrat your observations with enron-emails.txt.) How many words are there in Fathers and Sons by Ivan Turgenev (turgenev.txt)? How many instances are there of the same word repeated twice? How many words in the dictionary (words.txt; it’s actually an inflectional lexicon) have their letters in alphabetical order? How many of the nine letter words (nines.txt)? • “Words” in Fathers and Sons, according to wc: 74 242 • Same “word” repeated twice: 9-11, depending on how stringently you define word boundaries • Words in words.txt with letters in alphabetical order: 547 • Nine-letter words (nines.txt) with letters in alphabetical order: 94 (although none of them are really “words”, per se)

2