Artificial Intelligence Master’s Thesis by Srijani Kirti Thesis Supervisor Prof. Ashay Dharwadker Ansal Institute of Technology 15th April 2004 Abstract This thesis is a survey of the field of Artificial Intelligence vis-à-vis natural language communication between humans and machines. We start with the Turing Test as a definition of AI. We then explore Chomsky’s concept of Universal Grammar. Is it really possible to design a machine that passes the Turing Test? We study the famous Eliza program written by Weizenbaum, its grammar and transformation rules.  Finally, we implement the Eliza program in C++ and give an overview of how our version of the  program works. A detailed manual and sample conversations with Eliza are included in the appendix. The source code of the software is provided under the GNU public license for noncommercial use on the accompanying CD. Contents 1. The Turing Test 2. Noam Chomsky’s Universal Grammar 3. Chatbot Eliza 4. Overview of how the program works 5. Actual Code 6. Analysis of the code 7. Appendix – Eliza Manual 8. Appendix – Conversations with Eliza 9. References

Prof. Ashay Dharwadker's Courses (3):

Course	Semester	Grade	Add New Course
MS Project	Fall 2003	View	Update Course
Database Systems	Fall 2003	View	Update Course
Computer Networks	Spring 2004	View	Update Course

Projects (2)

Reference: Weizenbaum's original paper

Seminars (2)

• How Eliza works:
• User gives input statement S.
• S is examined for key words (key words are ranked).
• S is transformed according to rules associated with keywords.
• Transformation rules are also specified for content-free statements.
• Transformed S is output by Eliza.
• Technical Problems:
• Identify the "most important" key word in S.
• Identify the context of key word, e.g. if "YOU" is followed by "ARE" then the context is that an assertion is being made.
• Choice of transformation rule.
• Making Eliza respond "intelligently" when no key word is found.
• Editing, extension of Eliza program (we call this "Educating Eliza").
• Example of Transformation:
• Input S="IT SEEMS THAT YOU HATE ME"
• Template

1	2	3	4
IT SEEMS THAT	YOU	HATE	ME

• Identification of key words: 2, 4. Nothing else is understood by Eliza.
• Decomposition rule: __ YOU __ ME
• Reassembly rule: Change YOU to I and ME to YOU. Replace the first blank by the stock phrase "WHAT MAKES YOU THINK", replace the second blank by 3:

Stock Phrase	2'	3	4'
WHAT MAKES YOU THINK	I	HATE	YOU

• Output S'="WHAT MAKES YOU THINK I HATE YOU".
• Transformation Tree Diagram:

Research Notes (5)

Biography

• At MIT
• At MNSU emuseum

On linguistics

• Chomsky Archive
• A New Twist

Criticisms

• At Berkeley
• Semi-Daily Journal

In 1989, the ARPANET was renamed "Internet," which had also been described as the "information superhighway." These days, the Internet continues to expand, stringing together the World Wide Web, an all-encompassing, affordable, universal communications network.

Rules (1)-(8) do not operate in isolation but constitute an integrated system. The symbol S (standing mnemonically for "sentence") is designated as the initial symbol. This information is not given in the rules (1)-(8), but it can be assumed either that it is given in a kind of protocol statement preceding the grammatical rules or that there is a universal convention according to which S is always the initial symbol. It is necessary to begin with a rule that has the initial symbol on the left. Thereafter any rule may be applied in any order until no further rule is applicable; in doing so, a derivation can be constructed of one of the sentences generated by the grammar. If the rules are applied in the following order: (1), (2), (3), (3), (4), (5), (5), (6), (6), (7), (8), then assuming that "the" is selected on both applications of (5), "man" on one application of (6), and "ball" on the other, "will" on the application of (7), and "hit" on the application of (8), the following derivation of the sentence "The man will hit the ball" will have been constructed:
Many other derivations of this sentence are possible, depending on the order in which the rules are applied. The important point is that all these different derivations are equivalent in that they can be reduced to the same tree diagram shown below.

fig4 If this is compared with the system of rules, it will be seen that each application of each rule creates or is associated with a portion (or subtree) of the tree. The tree diagram, may now be considered as a structural description of the sentence "The man hit the ball." It is a description of the constituent structure, or phrase structure, of the sentence, and it is assigned by the rules that generate the sentence.
Till now i’ve only been explaining phrase-structure grammar consisting entirely of phrase-structure rules. However, a Transformational grammar (as formalized by Chomsky) includes both phrase-structure and transformational rules (as well as morphophonemic rules). The transformational rules depend upon the prior application of the phrase-structure rules and have the effect of converting, or transforming, one phrase marker into another. What is meant by this statement may be clarified first with reference to a purely abstract and very simple transformational grammar, in which the letters stand for constituents of a sentence (and S stands for "sentence"):
The first five rules are phrase-structure rules (PS rules); rule (6) is a transformational rule (T rule). The output of rules (1)-(5) is the terminal string a + b + c + e + f + d + g + h, which has associated with it the structural description indicated by the phrase marker shown in Figure 5 (left). Rule (6) applies to this terminal string of the PS rules and the associated phrase marker. It has the effect of deleting C (and the constituents of C) and permuting A and D (together with their constituents). The result is the string of symbols d + g + h + a + b, with the associated phrase marker shown in the following figure.

The phrase marker shown in the figure (left) may be described as underlying, and the phrase marker shown in the Figure(right) as derived with respect to rule (6). One of the principal characteristics of a transformational rule is its transformation of an underlying phrase marker into a derived phrase marker in this way. Transformational rules, in contrast with phrase-structure rules, are also formally more heterogeneous and may have more than one symbol on the left-hand side of the arrow. The linguistic importance of these abstract considerations may be explained with reference to the relationship that holds in English between active and passive sentences.
Chomsky's rule for relating active and passive sentences (as given in Syntactic Structures) is very similar, at first sight, to Harris's, discussed above. Chomsky's rule is:
This rule, called the passive transformation, presupposes and depends upon the prior application of a set of phrase-structure rules. For simplicity, the passive transformation may first be considered in relation to the set of terminal strings generated by the phrase-structure rules (1)-(8) given earlier. The string "the + man + will + hit + the + ball" (with its associated phrase marker, as shown in Figure 4) can be treated not as an actual sentence but as the structure underlying both the active sentence "The man will hit the ball" and the corresponding passive "The ball will be hit by the man." The passive transformation is applicable under the condition that the underlying, or "input," string is analyzable in terms of its phrase structure as NP - Aux - V - NP (the use of subscript numerals to distinguish the two NPs in the formulation of the rule is an informal device for indicating the operation of permutation). In the phrase marker in Figure 4 "the" + "man" are constituents of NP, "will" is a constituent of Aux, "hit" is a constituent of V, and "the" + "ball" are constituents of NP. The whole string is therefore analyzable in the appropriate sense, and the passive transformation converts it into the string "the + ball + will + be + en + hit + by + the + man." A subsequent transformational rule will permute "en + hit" to yield "hit + en," and one of the morphophonemic rules will then convert "hit + en" to "hit" (as "ride + en" will be converted to "ridden"; "open + en" to "opened," and so on).
Every transformational rule has the effect of converting an underlying phrase marker into a derived phrase marker. The manner in which the transformational rules assign derived constituent structure to their input strings is one of the major theoretical problems in the formalization of transformational grammar. Here it can be assumed not only that "be + en" is attached to Aux and "by" to NP (as indicated by the plus signs in the rule as it has been formulated above) but also that the rest of the derived structure is as shown in Figure 6.

Fig 6 The phrase marker in Figure 6 formalizes the fact, among others, that "the ball" is the subject of the passive sentence "The ball will be hit by the man," whereas "the man" is the subject of the corresponding active "The man will hit the ball" (cf. Figure 4)
. Although the example above is a very simple one, and only a single transformational rule has been considered independently of other transformational rules in the same system, the passive transformation must operate, not only upon simple noun phrases like "the man" or "the ball," but upon noun phrases that contain adjectives ("the old man"), modifying phrases ("the man in the corner"), relative clauses ("the man who checked in last night"), and so forth. The incorporation, or embedding, of these other structures with the noun phrase will be brought about by the prior application of other transformational rules. It should also be clear that the phrase-structure rules require extension to allow for the various forms of the verb ("is hitting," "hit," "was hitting," "has hit," "has been hitting," etc.) and for the distinction of singular and plural.
It is important to note that, unlike Harris's, Chomsky's system of transformational grammar does not convert one sentence into another: the transformational rules operate upon the structures underlying sentences and not upon actual sentences. A further point is that even the simplest sentences (i.e.,kernel sentences) require the application of at least some transformational rules. Corresponding active and passive sentences, affirmative and negative sentences, declarative and interrogative sentences, and so on are formally related by deriving them from the same underlying terminal string of the phrase-structure component. The difference between kernel sentences and nonkernel sentences in Syntactic Structures (in Chomsky's later system the category of kernel sentences is not given formal recognition at all) resides in the fact that kernel sentences are generated without the application of any optional transformations. Non kernel sentences require the application of both optional and obligatory transformations, and they differ one from another in that a different selection of optional transformations is made.
http://www.ifi.unizh.ch/groups/CL/volk/SyntaxVorl/Chomsky.html
http://www.zompist.com/lang9.html