Intelligent Systems by Universal Teacher Publications

Chomsky Hierarchy of Generative Grammars

Q. Give an example of four types 0, 1, 2, and 3 for Chomsky's hierarchy of generative grammars.
OR
Q. Explain the main differences between the Chomsky's hierarchy of generative grammars & Fillmore's Case Grammer.

Ans. Noam Chomsky defined a hierarchy of grammars he called types 0, 1, 2, and 3.

Type 0 grammar: It is the most general grammar. It is obtained by making the simple restriction that y cannot be the empty string in the rewrite form xyz à xwz. This broad generality requires that a computer having the power of a Turing machine be used to recognize sentences of type 0.

Type 1 grammar: It is known as context-sensitive grammars. They have the added restriction that the length of the string on the right-hand side of the rewrite rule must be at least as long as the string on the left-hand side. Furthermore, in productions of the form xyz à xwz, y must be a single nonterminal symbol and w, a nonempty string. Typical rewrite rules for type} grammars take the forms

S à aS
S à aAB
AB à BA
aA à ab
aA à aa

where the capitalized letters are nonterminals and the lower case letters terminals.

Type 2 grammar: It is known as a context-free grammar. It is characterized by rules with the general form <symbol> à <symbol}> ... <symbolk> where k ³ 1 and where the left-hand side is a single nonterminal symbol, A à xyz where A is a single nonterminal. Productions for this type take forms such as

S à aS
S à aSb
S à aB
S à aAB
A à a
B à b

Type 3 Grammar: It is known as finite state or regular grammar, whose rules are characterized by the forms

A à aB
A à a

The languages generated by these grammars are also termed types 0, 1 (context- sensitive), 2 (context-free), and 4 (regular) corresponding to the grammars which generate them.

Fillmore's Case Grammar

Case grammars use the functional relationships between noun pharases and verbs to reveal the deeper case of a sentence. These grammars use the fact that verbal elements provide the main source of structure in a sentence since they describe the subject and objects.

In case grammars, a sentence is defined as being composed of a proposition P, a tenseless set of relationships among verbs and noun phrases and a modality constituent M, composed of mood, tense, aspect, negation, and so on. Thus, a sentence can be represented as

S à M + P

where p in turn consists of one or more distinct cases C1 , C2, ….., CK,

P à C1 + C2 + ….. + CK.

The number of cases suggested by Fillmore were relatively few. For example, the original list contained only some six cases. They relate to the actions performed by agents, the location and direction of actions, and so on. For example, the case of an instigator of an action is the agentive (or agent), the case of an instrument or object used in an action is the instrumental, and the case of the object receiving the action or change is the objective. Thus, in sentences like "The soldier struck the suspect with the rifle butt' , the soldier is the agentive case, the suspect the objective case, and the rifle butt the instrumental case. Other basic cases include dative (an animate entity affected by an action), factitive (the case of the object or of being that which results from an event), and locative (the case of location of the event).

Case frames are provided for verbs to identify allowable cases. They give the relationships which are required and those which are optional. For the above sentence. a case frame for the verb struck might be

STRUCK[OBJECTIVE (AGENTIVE) (INSTRUMENTAL)]

This may be interpreted as stating that the verb struck must occur in sentences with a noun phrase in the objective case and optionally (parentheses indicate optional use) with noun phrases in the agentive and instrumental cases.

A tree representation for a case grammar will identify the words by their modality and case. For example, a case grammar tree for the sentence "Sue did not take the car" is illustrated in the following figure:

AI Contents