Specifying a set by listing its members. The specification of the membership of a set completely characterises the set. A set may be specified by listing its members, or by specifying particular properties or attributes the members must have in order that they be considered members of the set. For example, the set of things on my desk may be specified by listing these things as follows:

{mug,pencil,paper,dictionary,eraser,lamp,elbow,dust}

A letter may be used to name or represent a set, as

D = {mug,pencil,paper,dictionary,eraser,lamp,elbow,dust}

The order in which elements are listed is not important. Thus, we can represent the set D by listing its elements as follows:

D = {elbow,mug,lamp,paper,dictionary,dust,pencil,eraser}

D = {elbow,elbow,mug,lamp,paper,pencil,dictionary,dust,pencil,eraser,pencil}

Note that neither D itself, nor the list of its elements is the set: D denotes or identifies the set, and the list merely denotes or identifies its members. Furthermore, the words in D identify objects. If we wanted to refer to the words themselves, we would enclose them in apostrophes, also know as single quote marks, as in the following example

D_w = {'mug','pencil','paper','dictionary','eraser','lamp','elbow','dust'}

Specifying a set by identifying a property of its members. The foregoing examples illustrate the specification of sets by listing their members. A set also may be specified by citing an attribute or property comprising a criterion on the basis of which things are collected together as a set. For example, the set of things on my desk may be specified as

D = {d | d a thing on my desk}

Identifying a member of a set. The statement that my elbow is a member or element of the set D may be written

elbow Î D

The symbol Ï denotes the negation of Î , and is read " is not an element of", " is not a member of", or "does not belong to". Thus, it would be used in a statement such as

computer Ï D

Subset of a set. It is possible to talk about subsets of sets. For example, suppose we want to consider only those elements of D that are used in writing and that someone might describe as writing tools or materials. Then, we might specify this set of writing tools or materials as follows:

M = {m | m Î D, m used in writing}

M = {paper,pencil}

M Í D

D Ê M

Note that the symbols Í and Ê denote a relationship among sets, or a relation on sets. The symbol Î , however, denotes a relation between elements and sets. For example, we can write

paper,pencil Î D

{paper,pencil} Í D

paper Î {paper} Í M

Proper subset of a set. Since the set D contains elements that are not members of M, we can say the M is a proper subset of D and write

M Ì D

D É M

Equality of sets. The horizontal line added beneath É and Ì , which yields the symbols Ê and Í , respectively, indicates the possibility that two sets might be equal. For example, we can write

D Ê D

X = Y

Equivalence of sets. It is also possible to speak of equivalent sets. Two sets are said to be equivalent if and only if they contain the same number of elements. For example, the set D of things on my desk, and the set D_w of words identifying the things on my desk, are equivalent because we can match each word in D_w with a thing in D. We can state this relation between the two sets by writing

D_w º D

D_w ¹ D

M ¹ D

The specification of the set M is rather vague and open to alternative interpretations. Someone might, for example, consider that the eraser should be included, along with the pencil and paper, because it is obviously used in writing. Consequently, this person will interpret the specification as actually meaning the set M_e where

M_e = {eraser,pencil,paper}

Suppose another person thinks that the erase should not be included, but she claims she cannot write without a dictionary. Hence, she construes the specification of materials used in writing as meaning the set

M_d = {dictionary,paper,pencil}

M_d ¹ M_e

M = M_d Ç M_e

In general, the intersection of any two sets X and Y is the set of all elements that are members of both X and Y. The set intersection operation is commutative, that is

X Ç Y = Y Ç X

(X Ç Y) Ç Z = X Ç (Y Ç Z)

The null set. If two sets share no elements in common, their intersection is the empty or null set, which is usually identified by the symbol Æ, or by writing {}. For example, suppose we consider the subset

M_c = {dust,elbow,mug,lamp}

M Ç M_c = Æ

The null set is a subset of any set so that, for example, we can write

Æ Ì M and Æ Ì M_c

X Ç Æ = Æ

Union of sets. In identifying the set of those elements of D that are used in writing, one of the two individuals included the dictionary, in addition to the paper and pencil, while the other included the eraser. Thus, the four items, the paper, pencil, eraser, and dictionary, were selected by one or the other of the two individuals as things used in writing. We might use M_u to name this set and identify its elements as follows

M_u = {paper,pencil,eraser,dictionary}

M_u = M_d È M_e

In general, the union of any two sets X and Y is the set of all elements that are members of either X or Y. Like the set intersection operation, set union is commutative, that is

X È Y = Y È X

(X È Y) È Z = Y È (X È Z)

Difference of sets. The individuals selecting the subsets M_e and M_d of D agree that the remaining elements, namely, those comprising the subset M_c consisting of the mug, lamp, elbow, and dust, cannot be considered as things used in writing. These things comprise a set consisting of those elements of D with the elements in the set M_u excluded or removed. We can identify this set as the difference between D and M_u, or as the complement of M_u relative to D. If the set M_c denotes this difference, or relative complement set, we can define it as follows:

M_c = D - M_u

Because M_u Í D, the difference operation entails that all the elements of M_u are removed from D. Thus, the intersection of M_c and M_u is the empty set so that we can write

M_c Ç M_u = Æ

The interpretation of the difference operation also means that we can obtain the complement of a set such as M_d relative to another set such as M_e. In this case, the removal from M_e of those elements that are also members of M_d leaves the singleton set {eraser}.

M_e - M_d = {eraser}

M_d - M_e = {dictionary}

Sets of sets. A set can also contain other sets as elements. For example, we can define a set M_de as consisting of the two sets M_d and M_e, that is

M_de = {M_d, M_e}

M_de = {{dictionary,paper,pencil}, {eraser,paper,pencil}}

Sets of words. The concepts and notation discussed above can be applied to sets of words. For example, consider the following sentence:

s = 'they stand by the bow and see her bow near the stand'

W = {w | w a word in s}

W = {'they','stand','by','the','bow','and','see','her','near'}

Subsets of words. We can identify several subsets of W. For example, we might consider the following subsets:

N = {w | w Î W, w a noun in s}
V = {w | w Î W, w a verb in s}

N = {'stand','bow'}
V = {'stand','bow','see'}

N Ì W and V Ì W

As a noun in s, 'bow' for example can identify the front end of a ship, a device for launching arrows, or a bending in general or of the head or body in a gesture of greeting or respect. As a verb, 'bow' might correspond to the action of bending in general or of the head or body to perform a gesture of greeting or respect. Since the two sets share elements in common, their intersection is not empty. In fact,

N Ç V = N

N È V = V
V - N = {'see'}

As the definitions of the sets N and V illustrate, the identification of such sets corresponds to the classification of the words in s according to their part of speech or lexical category. We can also specify other subsets of W on the same basis as follows:

PRO = {'they','her'}
DET = {'the'}
P = {'near','by'}
CONJ = {'and'}

Finite, infinite, denumerable, and countable sets. The sets illustrated above can all be described as finite; that is, they are either empty, or they consist of n distinct elements, where n denotes a whole number, usually called an integer, which is greater than zero. Thus, finite sets are equivalent to the set consisting of the first n positive integers, which is sometimes represented by writing

I_n = {1, 2, 3, ¼, n}

A set that is not finite is said to be infinite. There can be sets that are equivalent to the set of all positive integers, I₊, which may be represented by writing

I₊ = {1, 2, 3, ¼}

W × C = {áw,cñ | w Î W, c Î C}

áw,cñ for every w Î W and c Î C

w Î c

PRO ® they

they Î PRO

Then, if we were analysing a sentence such as

b = 'they see the bow'

PRO ® they	áthey, PROñ
V ® see	ásee, Vñ
DET ® the	áthe, DETñ
N ® bow	ábow, Nñ

F = {áthey, PROñ, ásee, Vñ, áthe, DETñ, ábow, Nñ}

{ áw, cñ | áw, cñ Î W × C, w Î c } .

Notice that the apostrophes used previously to distinguish words from the things they identify have been omitted because it is clear from the context that the lowercase letters on the right-hand sides of the rewriting rules and in the first entry of the ordered pairs are words.

S = {NP, VP},
NP = {DET, N, PRO}, and
VP = {V, NP} .

C × C × C = {áa,b,cñ | a,b,c Î C}

áNP, VP, Sñ	S ® NP VP
áDET, N, NPñ	NP ® DET N
áV, NP, VPñ	VP ® V NP

G = {áNP, VP, Sñ áDET, N, NPñ áV, NP, VPñ}

NP, VP Î, S
V, NP Î VP, and
DET, N Î NP .

Although C² × C = C³, the representation of the rule S ® NP VP as ááNP, VPñ, Sñ makes it clear that the two symbols on the right-hand side of the rule constitute an ordered pair. Thus, in addition to the condition that a simple English sentence consists of an NP and a VP (and not two NPs or two VPs), the pair áNP, VPñ can be seen as a statement that the subject NP of a simple English sentence precedes the predicate VP. Similarly, the pair áV, NPñ says that the object NP follows the verb in the VP, and áDET, Nñ states that the DET precedes the N in an NP.

The foregoing conditions thus restrict the elements of C³ to those listed in G. But since the subject noun phrase of the sentence b consists of a pronoun, we also require an ordered pair áPRO, NPñ Î C² corresponding to the rewriting rule NP ® PRO. Hence, we define a partial mapping H Í C² as follows:

H = {áPRO, NPñ}

The ordered pair in H, together with the ordered triples comprising the partial mapping G Í C³, and the ordered pairs making up the partial mapping F Í W × C permit us to define the set

R = F È G È H

Ordered n-tuples and strings. Before the elements of R can be applied to analyse b, however, it must be recognised that b is itself an ordered quadruple; that is, it is an element of W⁴. We can therefore show b as

b = áthey, see, the, bowñ Î W⁴

b = 'they see the bow'

Length of a string. The subscript numbers here serve only to distinguish the foregoing strings over W from b. The subscripts on b₁, b₂, and so on, however, also happen to correspond to the length of the string in each case. The length of a string is, naturally enough, defined to be the number of words it contains. The length of an arbitrary string a over W is denoted as | a | where

| a | = i if and only if a Î Wⁱ for 0 £ i £ n

g = d if and only if g_k = d_k for 1 £ k £ n = | g | = | d |

gd = dg if and only if g = d;
gd ¹ dg otherwise

gl = lg = g

Finite concatenative closure. Strings over a vocabulary such as W can, in principle, be of any length, provided they are finite. The set of all finite strings over W is denoted by W^*, where the superscript asterisk is called the Kleene star. This set might be represented by writing

W^* = {W⁰ ÈW¹ ÈW² ȼÈWⁿ}

gd Î W^* if and only if g, d Î W^*

'they stand' Î W^* and
'and' Î W^* means that
'they stand and' Î W^* and
'see her near' Î W^* means that
'they stand and see her near' Î W^* and
'the stand by the bow' Î W^* means that
'they stand and see her near the stand by the bow' Î W^*

The concept of a concatenative closure is not restricted to just sets or vocabularies of words such as W. One can also consider the closure of the set or vocabulary of category labels such as C, defined above as

C = {S, NP, VP, PRO, DET, P, CONJ, N, V}

b = áthey, see, the, bowñ Î W⁴

áPRO, V, DET, Nñ Î C⁴

áPRO, V, NPñ Î C³
áPRO, VPñ Î C²
áNP, VPñ Î C²
áSñ Î C¹

The analysis of the string b yields strings that are elements of he sets C¹, C², and C³. These sets are subsets of the finite concatenative closure C^* of the vocabulary of category labels C. Hence, all of the foregoing strings are elements of C^*. The closure C⁺ of C excluding the null string can also be defined

C⁺ = C^* - {l}

Notice that the string áPRO, V, DET, Nñ is the result of mapping all the words of b to their lexical categories. This element of C⁴ is thus the last in a sequence of strings which includes the following:

áPRO, see, the, bowñ Î C¹×W³
áPRO, V, the, bowñ Î C²×W²
áPRO, V, DET, bowñ Î C³×W¹

Partial mappings from words to category labels, and among category labels, can, in principle, be applied anywhere in a string. The only condition is that a substring of the string be an element of the domain of the mapping. Thus, the following strings might be produced in the course of analysis of b:

áthey, see, NPñ Î (C ÈW)³
áthey, VPñ Î (C ÈW)²
áSñ Î (C ÈW)¹

VP ® V, NP

Notice the difference between the double-shafted derivation arrow and the single-shafted rewriting arrow. The string on the right-hand side of the Þ derivation arrow is the string that results from applying a rewriting rule to the string to the left of the Þ. The string on the left-hand side includes a substring, consisting of the single category label VP in this example, that matches the left-hand side of the rewriting rule VP ® V, NP. The label VP is replaced by the string V NP on the right-hand side of the rewriting rule to produce the string áNP, V, NPñ on the right of the Þ derivation arrow. Thus, the strings on either side of the derivation arrow are just strings before and after the application of a rewriting rule.

S Þ^* s, where s Î W^*

Note that Þ^* includes the application of no rewriting rules so that we can actually write something such as

áNP, VPñÞ^* áNP, VPñ

S Þ⁺ s, where s Î W⁺

The notion of a derivation has been introduced above in the context of applying rewriting rules, although we have continued to represent strings using the ordered n-tuple notation. In the context of partial mappings, rather than rewriting rules, derivations correspond to reductions; that is, strings of words are reduced to a string consisting of the sentence category label. Of course, a string s Î W⁺ can be reduced to S Î C if and only if s is a sentence, and we can write

sÜ⁺ S, where s Î W⁺

sÜ^* S, where s Î W^*

áV, NP, VPñ

áNP, V, NPñÜ áNP, VPñ

Terminal and non-terminal vocabularies. The particular sets C and W of category labels and words, respectively, have been used to provide concrete examples for concepts and notation discussed above. Generally, the names S (the uppercase Greek letter sigma) or V_T is used to identify the vocabulary, or a subset of the vocabulary of a language. The subscript T is appended to V in V_T because the words comprising the vocabulary are often called terminal symbols. The term "terminal" is used because strings consisting exclusively of words are the end result of a derivation. The term "symbol" is used to include both the words and the category labels that are processed during a derivation. The category labels are identified as "non-terminal symbols" or as variables, and they comprise the non-terminal vocabulary, V_N. (When the vocabulary of words or terminal symbols is identified using S, then vocabulary of non-terminal symbols or variables is sometimes identified simply as V.) The two vocabularies are normally disjoint, that is,

V_T ÇV_N = Æ

B ® b, where b Î V_T, B Î V_N
A ® a, where a Î V_N^*, A Î V_N

áb, Bñ, where b Î V_T, B Î V_N
áa, Añ, where a Î V_N^*, A Î V_N

Generative grammar. A set of partial mappings or rewriting rules such as those illustrated here, together with the terminal and non-terminal vocabularies V_T and V_N, respectively, comprise a grammar. Such grammars are also called generative grammars because sentences can be thought of as being generated from the sentence category label by applying the rewriting rules. These grammars are also called phrase-structure grammars or constituent-structure grammars because they are based upon the notion of sentence constituents or phrases such as the noun and verb phrases. A generative or phrase-structure grammar G is defined by an ordered quadruple

G = áV_N, V_T, S, Pñ

Language generated by a grammar. A string s Î V_T^* that can be derived from the sentence category label S Î V_N by the rewriting rules in P, or which can be reduced to a string áSñ consisting of only the sentence category label by the corresponding partial mappings, is said to be a sentence generated by G. The set of all such strings is described as the language generated by G, denoted as as L(G), where

L(G) = {s | s Î V_T^*, S Þ^*s}

L(G) = {s | s Î V_T^*, sÜ^*áSñ}

Linguistics 484

Notes Index

Top of Page