Lab 2b Rules & Answers

Modifications to the grammar and lexicon
2.1
To handle verbs that take no arguments, one, two etc arguments, I created subcategories instead of the generic V_ROOT

These are
TRANSITIVE_1 (can take one argument) TRANSITIVE_2 (can take two arguments e.g. send) INTRANSITIVE (don’t take arguments)

2.1Lex
Begin: N_ROOT TRANSITIVE_1 TRANSITIVE_2 INTRANSITIVE DET PREP End
N: N_SUFFIX End
VTrans1: V_SUFFIX
VTrans2: V_SUFFIX
VIntrans: V_SUFFIX
Suffix: End

N_ROOT:
cat N "N"
guy N "N"
pajama N "N"
poirot N "N"
solution N "N"
police N "N"
detective N "N"
case N "N"
gun N "N"
telescope N "N"
hill N "N"

N_SUFFIX:
+s Suffix ""

PREP:
on End "P"
in End "P"
with End "P"
to End "P"

DET:
the End "Det"
a End "Det"
an End "Det"
some End "Det"

TRANSITIVE_1:
solve VTrans1 "VTrans1"
send VTrans1 "VTrans1"
sent VTrans1 "VTrans1"
lose VTrans1 "VTrans1"
lost VTrans1 "VTrans1"
see VTrans1 "VTrans1"
saw VTrans1 "VTrans1"

TRANSITIVE_2:
send VTrans2 "VTrans2"
sent VTrans2 "VTrans2"

INTRANSITIVE:
think VIntrans "VIntrans"
thought VIntrans "VIntrans"

V_SUFFIX:
+ed Suffix ""
+s Suffix ""
'' Suffix ""
+er N "N"
'' End None

End:
'#' Begin None
I added these rules
VP -> VTrans1 Det N
VP -> VTrans1 N
To resolve the issue of a verb taking one NP argument and differentiating that from a verb that takes two argument in the form of NP PP
In addition to
VP -> VTrans2 NP PP

The grammar file is as follows

%kimmo "/mit/mujde/Desktop/english2b.lex" "/mit/mujde/Desktop/english2b.rul"

---- Rules -----
Start -> S
S -> NP VP
NP -> N
NP -> Det N
NP -> Det N PP
VP -> VIntrans
VP -> VTrans1 Det N
VP -> VTrans2 NP PP
PP -> P NP
VP -> VTrans1 N

2.2 Verbs That Take Full Sentences As Arguments

I added yet another subcategory for verbs like believe that take full sentences as grammars namely
TRANSITIVE_3
In addition I grouped “To be” verbs together (under a verb category VSTATE) ,added Comp (for “that”) and the adjective entry for “incompetent”

The lex for this part of lab is

Begin: N_ROOT TRANSITIVE_1 TRANSITIVE_2 TRANSITIVE_3 INTRANSITIVE DET PREP COMP ADJ BE End
N: N_SUFFIX End
VTrans1: V_SUFFIX
VTrans2: V_SUFFIX
VTrans3: V_SUFFIX
VIntrans: V_SUFFIX
Suffix: End
Comp: End
Adj: End
Be: End

N_ROOT:
cat N "N"
guy N "N"
pajama N "N"
poirot N "N"
solution N "N"
police N "N"
detective N "N"
case N "N"
gun N "N"
telescope N "N"
hill N "N"

N_SUFFIX:
+s Suffix ""

PREP:
on End "P"
in End "P"
with End "P"
to End "P"

DET:
the End "Det"
a End "Det"
an End "Det"
some End "Det"

TRANSITIVE_1:
solve VTrans1 "VTrans1"
send VTrans1 "VTrans1"
sent VTrans1 "VTrans1"
lose VTrans1 "VTrans1"
lost VTrans1 "VTrans1"
see VTrans1 "VTrans1"
saw VTrans1 "VTrans1"

TRANSITIVE_2:
send VTrans2 "VTrans2"
sent VTrans2 "VTrans2"

TRANSITIVE_3:
believe VTrans3 "VTrans3"

INTRANSITIVE:
think VIntrans "VIntrans"
thought VIntrans "VIntrans"

BE:
was Be "VState"
were Be "VState"
is Be "VState"
are Be "VState"

COMP:
that Comp "Comp"

ADJ:
incompetent Adj "Adj"

V_SUFFIX:
+ed Suffix ""
+s Suffix ""
'' Suffix ""
+er N "N"
'' End None

End:
'#' Begin None


The change in grammar is as follows
We add a new verb phrase rule for the new verb subcategory which takes a Sbar as an argument
VP -> VTrans3 Sbar
An Sbar is a full sentence that may be preceded by a complementizer which is either “that” (coming from lexicon) or “a space”. To parse the S part of our Sbar we add yet another rule which can parse sentences with verb “to be” and adjectives
Sbar -> Comp S
Comp ->
S -> NP VState Adj

And the grammar file

%kimmo "/mit/mujde/Desktop/2.12.4/2.3/kurallar/22end.lex" "/mit/mujde/Desktop/english2b.rul"

---- Rules -----
Start -> S
S -> NP VP
NP -> N
NP -> Det N
NP -> Det N PP
VP -> VIntrans
VP -> VTrans1 Det N
VP -> VTrans1 N
VP -> VTrans2 NP PP
VP -> VTrans3 Sbar
Sbar -> Comp S
PP -> P NP
Comp ->
S -> NP VState Adj

2.3 Unbounded dependencies and questions

(Outputs for the examples in this section are merged with the grammar in 2.4)
Step 1
To parse sentences such as “poirot did solve the case”
I modified both the lexicon and the grammar. I added subcategories for verbs such as TTRANSITIVE which are tense-less verbs e.g.

TTRANSITIVE_2:
send VTTrans2 "I_VTrans2"
So that we can ensure our verb has no tense. This leads to a doubling of verb entries in the cases unless the verb is inflected in a visible way (e.g. sent, thought etc). So the verb “send “ would be both in TRANSITIVE_2 (verbs that can have tenses) and TTRANSITIVE_2 (verbs with no tense marker)
We also need to add Aux (“did”)
A doubling in grammar occurs to accommodate the new kind of “tenseless” verb phrases. For every VP rule we have, we expand the grammar with corresponding rules forming I_VP (tenseless VPs)
Finally add the S -> NP Aux I_VP rule to parse the form we need

Step 2
To allow question formation as in "did poirot solve the case"
We just add the rule
S -> Aux NP I_VP

Step 3
We need to add the possibility to treat phrases such as “which cases” as NPs
NP -> WhNP
We add rules for two possible ways to form a WhNP
WhNP -> WhIn (stands for “who” in lexicon)
WhNP -> WhDet N (WhDet stands for which in the lexicon)
Step 4
To parse sentences such as “which cases did Poirot solve?”

We add the rule
S -> Comp-Wh S-WhNP

Comp-Wh must be a non-null WhNP (as opposed to the “gap” WhNp). We also need to account for the possibility of VPs with “gaps” in them as “did Poirot solve [gap]”. This is done via the rules expanding VP-WhNP
Comp-Wh -> WhNP
S-WhNP -> Aux NP VP-WhNP

VP-WhNP -> I_VTrans1 WhNpf
VP-WhNP -> I_VTrans2 WhNpf PP
VP-WhNP -> I_VTrans3 Comp Sbar-Wh


Sbar -> Comp-Wh Sbar-Wh
Sbar -> Comp S
These are to parse sentences such as “which cases did Poirot believe that the detectives sent to the police”
Sbar-Wh -> NP VP-Sbar
VP-Sbar -> VTrans3 Comp Sbar-Wh
VP-Sbar -> VTrans2 WhNPf PP
VP-Sbar -> VTrans1 WhNPf
Gaps are denoted by WhNPf symbol
WhNPf ->

The full grammar for the end of this section is
%kimmo "/mit/mujde/Desktop/2.3biktim.lex" "/mit/mujde/Desktop/english2b.rul"
---- Rules -----
Start -> S
S -> Aux NP I_VP
S -> NP VP
S -> Comp-Wh S-WhNP
S-WhNP -> Aux NP VP-WhNP

VP-WhNP -> I_VTrans1 WhNpf
VP-WhNP -> I_VTrans2 WhNpf PP
VP-WhNP -> I_VTrans3 Comp Sbar-Wh
I_VP -> I_VIntrans
I_VP -> I_VTrans1 Det N
I_VP -> I_VTrans1 N
I_VP -> I_VTrans2 NP PP
I_VP -> I_VTrans3 Sbar
Sbar -> Comp-Wh Sbar-Wh
Comp-Wh -> WhNP
NP -> N
NP -> Det N
NP -> Det N PP
WhNP -> WhIn
NP -> WhNP
VP -> VIntrans
VP -> VTrans1 Det N
VP -> VTrans1 N
VP -> VTrans2 NP PP
VP -> VTrans3 Sbar
Sbar -> Comp S
VP-Sbar -> VTrans3 Comp Sbar-Wh
VP-Sbar -> VTrans2 WhNPf PP
VP-Sbar -> VTrans1 WhNPf
Sbar-Wh -> NP VP-Sbar
WhNPf ->
PP -> P NP
Comp ->
S -> NP VState Adj
S -> NP Aux I_VP
Aux -> DO
WhNP -> WhDet N

2.4 Agreement, features and grammar size

I used the approach of enumerating agreements as separate nonterminals such as NPp (a plural NP), NPs and NPb (an NP that can be both such as “who”)

Additionally, to get outputs with these forms from the lexicon, I made the following revisions
If a noun has no plural mark, it is output as plain N, but if it has the “s” suffix it is output from pykimmo as Np. Determinants are grouped readily, “a”, “an” is a singular Det (Dets) whereas “the” and “some” can determine both plural and singular NPs -output as Detb.

We modify the suffixes for verb slightly. Every verb group has its own groups of suffix for now to allow final parses specific to the verb group.
e.g. a VTrans2 (e.g. send) can take the suffix V_SUFFIX2
TRANSITIVE_2:
send VTrans2 "VTrans2"
sent VTrans2 "VTrans2b"

VTrans2: V_SUFFIX2

V_SUFFIX2:
+ed Suffix "VTrans2b"
+s Suffix "VTrans2s"
'' Suffix ""
+er N "N"
'' End None

So if pykimmo recognizes sent, it outputs it as “VTrans2b” (a verb that can take agree with both plural and singular NPs). Note that in this example, the possibility of “+ed” is incorrect but shown here for demonstrational purposes, if any verb takes athe past tense form it can be preceded by a plural/singular NP. If it takes the suffix s, it can only take singular NPs, if it has no suffix, it can be used with plural NPs. (e.g. they send)

The final lex is as follows



Begin: N_ROOT TRANSITIVE_1 TRANSITIVE_2 TRANSITIVE_3 INTRANSITIVE TTRANSITIVE_1 TTRANSITIVE_2 TTRANSITIVE_3 TINTRANSITIVE DET PREP COMP ADJ BE AUX WHDET WHO End
N: N_SUFFIX End
VTrans1: V_SUFFIX1
VTrans2: V_SUFFIX2
VTrans3: V_SUFFIX3
VIntrans: V_SUFFIX4
Suffix: End
Comp: End
Adj: End
Be: End
Do: End
VTTrans1: End
VTTrans2: End
VTTrans3: End
VTIntrans: End
WhDet: End
WhIn: End

N_ROOT:
cat N "N"
guy N "N"
pajama N "N"
poirot N "N"
solution N "N"
police N "N"
detective N "N"
case N "N"
gun N "N"
telescope N "N"
hill N "N"

N_SUFFIX:
+s Suffix "Np"

PREP:
on End "P"
in End "P"
with End "P"
to End "P"

DET:
the End "Detb"
a End "Dets"
an End "Dets"
some End "Detb"

TRANSITIVE_1:
solve VTrans1 "VTrans1"
send VTrans1 "VTrans1"
sent VTrans1 "VTrans1b"
lose VTrans1 "VTrans1"
lost VTrans1 "VTrans1b"
see VTrans1 "VTrans1"
saw VTrans1 "VTrans1b"

TTRANSITIVE_1:
see VTTrans1 "I_VTrans1"
lose VTTrans1 "I_VTrans1"
solve VTTrans1 "I_VTrans1"
send VTTrans1 "I_VTrans1"

TRANSITIVE_2:
send VTrans2 "VTrans2"
sent VTrans2 "VTrans2b"

TTRANSITIVE_2:
send VTTrans2 "I_VTrans2"


TTRANSITIVE_3:
believe VTTrans3 "I_VTrans3"


TRANSITIVE_3:
believe VTrans3 "VTrans3"

INTRANSITIVE:
think VIntrans "VIntrans"
thought VIntrans "VIntransb"

TINTRANSITIVE:
think VTIntrans "I_VIntrans"

BE:
was Be "VStates"
were Be "VStatep"
is Be "VStates"
are Be "VStatep"

COMP:
that Comp "Comp"

AUX:
did Do "DO"

ADJ:
incompetent Adj "Adj"

WHDET:
which WhDet "WhDet"
what WhDet "WhDet"

WHO:
who WhIn "WhIn"

V_SUFFIX1:
+ed Suffix "VTrans1b"
+s Suffix "VTrans1s"
'' Suffix ""
+er N "N"
'' End None

V_SUFFIX2:
+ed Suffix "VTrans2b"
+s Suffix "VTrans2s"
'' Suffix ""
+er N "N"
'' End None

V_SUFFIX3:
+ed Suffix "VTrans3b"
+s Suffix "VTrans3s"
'' Suffix ""
+er N "N"
'' End None

V_SUFFIX4:
+ed Suffix "VIntransb"
+s Suffix "VIntranss"
'' Suffix ""
+er N "N"
'' End None


End:
'#' Begin None

The final grm is

%kimmo "/mit/mujde/Desktop/2.3biktim2.lex" "/mit/mujde/Desktop/english2b.rul"
---- Rules -----
Start -> S
NPp -> Np
NPs -> N
NPs -> Detb N
NPp -> Detb Np
NPs -> Dets N
NPp -> Detb Np PP
NPs -> Detb N PP
NPs -> Dets N PP
NPb -> WhNPb
WhNPf ->
WhNPs -> WhDet N
WhNPp -> WhDet Np
WhNPb -> WhIn
Comp-Whs -> WhNPs
Comp-Whp -> WhNPp
NPp -> WhNPp
NPs -> WhNPs
Comp ->
Aux -> DO
PP -> P NPp
PP -> P NPs
PP -> P NPb

NPs -> N Comp Sbar-Wh
NPs -> Detb N Comp Sbar-Wh
NPs -> Dets N Comp Sbar-Wh
NPs -> Detb N PP Comp Sbar-Wh
NPs -> Dets N PP Comp Sbar-Wh

NPp -> Np Comp Sbar-Wh
NPp -> Detb Np Comp Sbar-Wh
NPp -> Detb Np PP Comp Sbar-Wh


VPb -> VIntransb
VPs -> VIntranss
VPp -> VIntrans
VPs -> VTrans1s Dets N
VPs -> VTrans1s Detb Np
VPs -> VTrans1s Detb N
VPp -> VTrans1 Dets N
VPp -> VTrans1 Detb Np
VPp -> VTrans1 Detb N
VPb -> VTrans1b Dets N
VPb -> VTrans1b Detb Np
VPb -> VTrans1b Detb N

VPs -> VTrans1s N
VPs -> VTrans1s Np
VPp -> VTrans1 N
VPp -> VTrans1 Np
VPb -> VTrans1b N
VPb -> VTrans1b Np

VPs -> VTrans2s NPs PP
VPs -> VTrans2s NPp PP
VPs -> VTrans2s NPb PP
VPp -> VTrans2 NPs PP
VPp -> VTrans2 NPp PP
VPp -> VTrans2 NPb PP
VPb -> VTrans2b NPs PP
VPb -> VTrans2b NPp PP
VPb -> VTrans2b NPb PP


VPb -> VTrans3b Sbar
VPs -> VTrans3s Sbar
VPp -> VTrans3 Sbar

I_VP -> I_VIntrans
I_VP -> I_VTrans1 Dets N
I_VP -> I_VTrans1 Detb Np
I_VP -> I_VTrans1 Detb N
I_VP -> I_VTrans1 Np
I_VP -> I_VTrans1 N
I_VP -> I_VTrans2 NPb PP

I_VP -> I_VTrans2 NPp PP
I_VP -> I_VTrans2 NPs PP
I_VP -> I_VTrans3 Sbar

VP-Sbarp -> VTrans3 Comp Sbar-Wh
VP-Sbarb -> VTrans3b Comp Sbar-Wh
VP-Sbars -> VTrans3s Comp Sbar-Wh

VP-Sbarp -> VTrans2 WhNPf PP
VP-Sbarb -> VTrans2b WhNPf PP
VP-Sbars -> VTrans2s WhNPf PP

VP-Sbarp -> VTrans1 WhNPf
VP-Sbarb -> VTrans1b WhNPf
VP-Sbars -> VTrans1s WhNPf

VP-WhNP -> I_VTrans1 WhNpf
VP-WhNP -> I_VTrans2 WhNpf PP
VP-WhNP -> I_VTrans3 Comp Sbar-Wh

S-WhNP -> Aux NPs VP-WhNP
S-WhNP -> Aux NPp VP-WhNP
S-WhNP -> Aux NPb VP-WhNP
Sbar -> Comp S

Sbar -> Comp-Whs Sbar-Wh
Sbar -> Comp-Whp Sbar-Wh

Sbar-Wh -> NPs VP-Sbars
Sbar-Wh -> NPp VP-Sbarp
Sbar-Wh -> NPs VP-Sbarb
Sbar-Wh -> NPp VP-Sbarb
Sbar-Wh -> NPb VP-Sbars
Sbar-Wh -> NPb VP-Sbarp
Sbar-Wh -> NPb VP-Sbarb



S -> Aux NPs I_VP
S -> Aux NPp I_VP
S -> Aux NPb I_VP

S -> NPs VPs
S -> NPp VPp
S -> NPs VPb
S -> NPp VPb
S -> NPb VPb
S -> NPb VPs
S -> NPb VPp

S -> Comp-Whs S-WhNP
S -> Comp-Whp S-WhNP



S -> NPs VStates Adj
S -> NPp VStatep Adj
S -> NPb VStates Adj
S -> NPb VStatep Adj


S -> NPs Aux I_VP
S -> NPp Aux I_VP
S -> NPb Aux I_VP



2.4.2a Grammar Size

The grammar size is 401

2.4.2b Comparison to grammar in 2.3

The grammar size for section 2.3 is 114
The grammer is roughly increased by 3.5 times.


2.5.2
For this part, in addition to the plural, singular feature, I added stuff such as finished (to mark a verb having tense as “fin”) and tense features in some cases.
These additions are superfluous and should not be taken into account for pluralization phenomenon. (e.g. We could have just assigned the tag I_VTransX to verbs without tense, as the information is already clear from the categorization I_VTransX instead of VTransX and verbs without tense can take any plural or singular NP)
The grammar file for this section
%kimmo "/mit/mujde/Desktop/25.lex" "/mit/mujde/Desktop/english2b.rul"
---- Rules -----
Start -> S
NP[plural ?x] -> N[plural ?x]
NP[plural ?x] -> Det[plural ?x] N[plural ?x]
NP[plural ?x] -> Det[plural ?x] N[plural ?x] PP
NP[plural ?x] -> WhNP[plural ?x]
WhNP[plural ?x] -> WhDet N[plural ?x]
WhNP -> WhIn
Comp ->
Aux -> DO
WhNPf ->
PP -> P NP
VP[plural ?x] -> VIntrans[fin +, plural ?x]
VP[plural ?x] -> VTrans1[fin +, plural ?x] Det N
VP[plural ?x] -> VTrans1[fin +, plural ?x] N
VP[plural ?x] -> VTrans2[fin +, plural ?x] NP PP
VP[plural ?x] -> VTrans3[fin +, plural ?x] Sbar
I_VP[fin ?x] -> I_VIntrans[fin ?x]
I_VP[fin ?x] -> I_VTrans1[fin ?x] Det N
I_VP[fin ?x] -> I_VTrans1[fin ?x] N
I_VP[fin ?x] -> I_VTrans2[fin ?x] NP PP
I_VP[fin ?x] -> I_VTrans3[fin ?x] Sbar
S -> Aux NP I_VP[fin -]
S[Agr ?x] -> NP[plural ?x] VP[plural ?x]
S -> Comp-Wh S-WhNP
S-WhNP -> Aux NP VP-WhNP
S -> NP Aux I_VP
S[Agr ?x] -> NP[plural ?x] VState[plural ?x] Adj

NP[plural ?x] -> NP[plural ?x] Comp Sbar-Wh


VP-WhNP -> I_VTrans1 WhNpf
VP-WhNP -> I_VTrans2 WhNpf PP
VP-WhNP -> I_VTrans3 Comp Sbar-Wh

Sbar -> Comp-Wh Sbar-Wh
Comp-Wh[plural ?x] -> WhNP[plural ?x]

Sbar -> Comp S
VP-Sbar -> VTrans3 Comp Sbar-Wh
VP-Sbar -> VTrans2 WhNPf PP
VP-Sbar -> VTrans1 WhNPf
Sbar-Wh -> NP VP-Sbar

And the lexicon is

Begin: N_ROOT TRANSITIVE_1 TRANSITIVE_2 TRANSITIVE_3 INTRANSITIVE TTRANSITIVE_1 TTRANSITIVE_2 TTRANSITIVE_3 TINTRANSITIVE DET PREP COMP ADJ BE AUX WHDET WHO End
N: N_SUFFIX End
VTrans1: V_SUFFIX
VTrans2: V_SUFFIX
VTrans3: V_SUFFIX
VIntrans: V_SUFFIX
Suffix: End
Comp: End
Adj: End
Be: End
Do: End
VTTrans1: End
VTTrans2: End
VTTrans3: End
VTIntrans: End
WhDet: End
WhIn: End

N_ROOT:
cat N "N[plural -]"
guy N "N[plural -]"
pajama N "N[plural -]"
poirot N "N[plural -]"
solution N "N[plural -]"
police N "N[plural -]"
detective N "N[plural -]"
case N "N[plural -]"
gun N "N[plural -]"
telescope N "N[plural -]"
hill N "N[plural -]"

N_SUFFIX:
+s Suffix "[plural +]"

PREP:
on End "P"
in End "P"
with End "P"
to End "P"

DET:
the End "Det"
a End "Det[plural -]"
an End "Det[plural -]"
some End "Det"

TRANSITIVE_1:
solve VTrans1 "VTrans1[fin -]"
send VTrans1 "VTrans1[fin -]"
sent End "VTrans1[fin +, tense past]"
lose VTrans1 "VTrans1[fin -]"
lost End "VTrans1[fin +, tense past]"
see VTrans1 "VTrans1[fin -]"
saw End "VTrans1[fin +, tense past]"

TTRANSITIVE_1:
see VTTrans1 "I_VTrans1[fin -]"
lose VTTrans1 "I_VTrans1[fin -]"
solve VTTrans1 "I_VTrans1[fin -]"
send VTTrans1 "I_VTrans1[fin -]"

TRANSITIVE_2:
send VTrans2 "VTrans2[fin -]"
sent End "VTrans2[fin +, tense past]"

TTRANSITIVE_2:
send VTTrans2 "I_VTrans2[fin -]"


TTRANSITIVE_3:
believe VTTrans3 "I_VTrans3[fin -]"


TRANSITIVE_3:
believe VTrans3 "VTrans3[fin -]"

INTRANSITIVE:
think VIntrans "VIntrans[fin -]"
thought End "VIntrans[fin +, tense past]"

TINTRANSITIVE:
think VTIntrans "I_VIntrans[fin -]"

BE:
was End "VState[fin +, tense past, plural -]"
were End "VState[fin +, tense past, plural +]"
is End "VState[fin +, tense present, plural -]"
are End "VState[fin +, tense present, plural +]"

COMP:
that Comp "Comp"

AUX:
did Do "DO"

ADJ:
incompetent Adj "Adj"

WHDET:
which WhDet "WhDet"
what WhDet "WhDet"

WHO:
who WhIn "WhIn"

V_SUFFIX:
+ed Suffix "[tense past, fin +]"
+s Suffix "[plural -, fin +]"
'' Suffix "[plural +, fin +]"
+er N "N[plural -]"
'' End None

End:
'#' Begin None


2.5.2.(2) Size Comparison of feature and non-feature based grammars
182 is the size of feature-based grammar (bar the superfluous fin)
Non feature based grammar’s size was 401, roughly 2.25 of the feature-based grammar


2.5.3(3)
Ordinary context free grammars

We can have rules as many as |previous grammar| * 2^m as in
VP ->V NPp
VP -> V NPb (both)
VP -> V NPs
Instead of only one rule VP-> V NP
The exact number is determined by how many rules are affected by the agreement features e.g. VPb, VPs, VPp
(To think about the number of affected rules, we also need to account for adjacency, in a basic sense, agreement of singularity/plurality depend on two adjacent nonterminals NP and VP)




Feature based context free grammars
We have two feature-value pairs in this example, in general too,we would have as much as 2m*|G| new rules with the addition of m binary-valued features
So for the size of grammar
Feature-less approach can grow exponantially, whereas feature-based grammars grow linearly
How to handle the lexicon ? We can just count the number of items in the lexicon and their feature value pairs size
So
e.g. sent V [past +, fin +]
would have an increase in size as 4.
that would mean the grammar would expand by an additional 2m*|G| in size.
That does not seem to be as significant as the grammar size growth in feature-less grammars. Because, still with the addition of lexicon in mind, the growth is linear in feature-based grammars
Also
How would that compare with denoting different outputs such as (Dets, Detb) from ordinary grammars? With pluralization we just needed a suffix, however if a feature value is something that cannot be readily determined by adding suffixes, the disadvantage of lexicon size increase in feature-based CFG may not be as important

2.6.1
it was very painful to write this one

Basicly, there are 3 different types of words
Ones which are fillers [whnp -, filler +]
Whdet N phrases such as "which cases" [whnp +, filler +]
All other non-filler, non whnp phrases [whnp -, filler -]

Verb phrases inherit their WhNp, filler status from the NP or Sbar they take as argument, and
to parse sentences such as this, which case did Poirot solve


S[Agr ?x] -> NP[WhNp ?x] Aux NP I_VP[WhNp ?x]


For the Ordinary S->NP VP, we need to add a twist for "which detectives solved the case" cases, this is done by setting filler feature -[no fillers]
S -> NP VP[filler -]


%kimmo "/mit/mujde/Desktop/forcesunited/26bubenimgecem.lex" "/mit/mujde/Desktop/english2b.rul"
---- Rules -----
Start -> S
NP[WhNp ?x] -> N[WhNp ?x]
NP[WhNp ?x] -> Det N[WhNp ?x]
NP[WhNp ?x] -> Det N[WhNp ?x] PP
NP[WhNp +, filler +] ->
NP[WhNp ?x] -> WhDet[WhNp ?x] N
NP[WhNp ?x] -> WhIn
Aux -> DO
Comp ->
PP -> P NP


VP[WhNp -] -> VIntrans
VP[WhNp ?x, filler ?y] -> VTrans1 NP[WhNp ?x, filler ?y]
VP[WhNp ?x, filler ?y] -> VTrans2 NP[WhNp ?x, filler ?y] PP

VP[WhNp ?x] -> VTrans3 Sbar[WhNp ?x]


I_VP[WhNp -] -> I_VIntrans
I_VP[WhNp ?x] -> I_VTrans1 NP[WhNp ?x]
I_VP[WhNp ?x] -> I_VTrans2 NP[WhNp ?x] PP

I_VP[WhNp ?y] -> I_VTrans3 Sbar[WhNp ?y]


S -> NP VState Adj
S-> Aux NP I_VP

S[Agr ?x] -> NP[WhNp ?x] Aux NP I_VP[WhNp ?x]



S -> NP VP[filler -]




S[Agr ?x] -> NP[WhNp ?x, filler +] Aux I_VP[WhNp ?x]


NP[WhNp -] -> Det N Comp Sbar
NP[WhNp -] -> N Comp Sbar
NP[WhNp -] -> Det N PP Comp Sbar

Sbar[WhNp ?x] -> Comp Sbar1[WhNp ?x]
Sbar1[WhNp ?x] -> NP VP[WhNp ?x]

and the lexicon file for both 2.6.1&

Begin: N_ROOT TRANSITIVE_1 TRANSITIVE_2 TRANSITIVE_3 INTRANSITIVE TTRANSITIVE_1 TTRANSITIVE_2 TTRANSITIVE_3 TINTRANSITIVE DET PREP COMP ADJ BE AUX WHDET WHO End
N: N_SUFFIX End
VTrans1: V_SUFFIX
VTrans2: V_SUFFIX
VTrans3: V_SUFFIX
VIntrans: V_SUFFIX
Suffix: End
Comp: End
Adj: End
Be: End
Do: End
VTTrans1: End
VTTrans2: End
VTTrans3: End
VTIntrans: End
WhDet: End
WhIn: End

N_ROOT:
cat N "N[WhNp -]"
guy N "N[WhNp -]"
pajama N "N[WhNp -]"
poirot N "N[WhNp -]"
solution N "N[WhNp -]"
police N "N[WhNp -]"
detective N "N[WhNp -]"
case N "N[WhNp -]"
gun N "N[WhNp -]"
telescope N "N[WhNp -]"
hill N "N[WhNp -]"

N_SUFFIX:
+s Suffix ""

PREP:
on End "P"
in End "P"
with End "P"
to End "P"

DET:
the End "Det[WhNp -]"
a End "Det[WhNp -]"
an End "Det[WhNp -]"
some End "Det[WhNp -]"


TRANSITIVE_1:
solve VTrans1 "VTrans1"
send VTrans1 "VTrans1"
sent End "VTrans1"
lose VTrans1 "VTrans1"
lost End "VTrans1"
see VTrans1 "VTrans1"
saw End "VTrans1"

TTRANSITIVE_1:
see VTTrans1 "I_VTrans1"
lose VTTrans1 "I_VTrans1"
solve VTTrans1 "I_VTrans1"
send VTTrans1 "I_VTrans1"

TRANSITIVE_2:
send VTrans2 "VTrans2"
sent End "VTrans2"

TTRANSITIVE_2:
send VTTrans2 "I_VTrans2"


TTRANSITIVE_3:
believe VTTrans3 "I_VTrans3"


TRANSITIVE_3:
believe VTrans3 "VTrans3"

INTRANSITIVE:
think VIntrans "VIntrans"
thought End "VIntrans"

TINTRANSITIVE:
think VTIntrans "I_VIntrans"

BE:
was End "VState"
were End "VState"
is End "VState"
are End "VState"

COMP:
that Comp "Comp"

AUX:
did Do "DO"

ADJ:
incompetent Adj "Adj"

WHDET:
which WhDet "WhDet[WhNp +]"


WHO:
who WhIn "WhIn[WhNp -]"

V_SUFFIX:
+ed Suffix ""
+s Suffix ""
'' Suffix ""
+er N ""
'' End None

End:
'#' Begin None

2.6.2
Compared to previous grammar, we need more extensive use of filler & WHNP features of prev. section.
WhNp & PP unification can be seen by the rules

S[Agr ?x, Agr ?y] -> PP[filler ?x, WhNp ?y] Aux NP I_VP[filler ?x, WhNp ?y]
S[Agr ?x, Agr ?y] -> NP[filler ?x, WhNp ?y] Aux NP I_VP[filler ?x, WhNp ?y]

In addition I made a twist
I_VP[WhNp +,filler +] -> I_VTrans2 NP[WhNp -, filler -, pp -] PP[WhNp -, filler +]
to bar NP PP phrases appearing together as an NP in utterances such as "send the gun to the police"

Grm file for 2.6.2

%kimmo "/mit/mujde/Desktop/forcesunited/262.lex" "/mit/mujde/Desktop/english2b.rul"
---- Rules -----
Start -> S
NP[filler ?x, WhNp ?y] -> N[filler ?x, WhNp ?y]
NP[filler ?x, WhNp ?y] -> Det N[filler ?x, WhNp ?y]
NP[filler ?x, WhNp ?y, pp +] -> Det N[filler ?x, WhNp ?y] PP[filler -, WhNp -]
NP[filler +, WhNp -] ->
NP[filler ?x, WhNp ?y] -> WhDet[filler ?x, WhNp ?y] N
NP[filler ?x, WhNp ?y] -> WhIn[filler ?x, WhNp ?y]
Aux -> DO
Comp ->

PP[filler ?x, WhNp ?y] -> P NP[filler ?x, WhNp ?y]

PP[filler ?x, WhNp ?y] -> P Wh[filler ?x, WhNp ?y]
PP[filler +, WhNp -] ->

S[Agr ?x, Agr ?y] -> PP[filler ?x, WhNp ?y] Aux NP I_VP[filler ?x, WhNp ?y]
S[Agr ?x, Agr ?y] -> NP[filler ?x, WhNp ?y] Aux NP I_VP[filler ?x, WhNp ?y]

VP[filler -] -> VIntrans
VP[filler ?y] -> VTrans1 NP[filler ?y]

VP[WhNp +, filler +] -> VTrans2 NP[WhNp -, filler +] PP[WhNp -, filler -]
VP[WhNp +, filler +] -> VTrans2 NP[WhNp -, filler -, pp -] PP[WhNp -, filler +]
VP[WhNp -, filler -] -> VTrans2 NP[WhNp -, filler -] PP[WhNp -, filler -]

VP[WhNp ?x, filler ?y] -> VTrans3 Sbar[WhNp ?x, filler ?y]

S[Agr ?x, Agr ?y] -> Aux NP[filler ?x, WhNp ?y] I_VP[filler ?x, WhNp ?y]
I_VP[filler -] -> I_VIntrans
I_VP[filler -, WhNp -] -> I_VTrans1 NP[filler -, WhNp -]
I_VP[filler +, WhNp +] -> I_VTrans1 NP[filler +, WhNp -]

I_VP[WhNp +,filler +] -> I_VTrans2 NP[WhNp -, filler +] PP[WhNp -, filler -]
I_VP[WhNp +,filler +] -> I_VTrans2 NP[WhNp -, filler -, pp -] PP[WhNp -, filler +]
I_VP[WhNp -,filler -] -> I_VTrans2 NP[WhNp -, filler -] PP[WhNp -, filler -]

I_VP[WhNp ?x, filler ?y] -> I_VTrans3 Sbar[WhNp ?x, filler ?y]

S -> NP VState Adj

S[Agr ?x] -> NP[filler ?x] VP[filler ?x]
S -> NP[WhNp +, filler +] VP[filler -]
S[Agr ?x] -> NP[filler ?x] Aux I_VP[filler ?x]

Sbar[WhNp ?x, filler ?y] -> Comp Sbar1[WhNp ?x,filler ?y]
Sbar1[WhNp +,filler +] -> NP VP[WhNp +,filler +]

and the lex file is

Begin: N_ROOT TRANSITIVE_1 TRANSITIVE_2 TRANSITIVE_3 INTRANSITIVE TTRANSITIVE_1 TTRANSITIVE_2 TTRANSITIVE_3 TINTRANSITIVE DET PREP COMP ADJ BE AUX WH WHDET WHO End
N: N_SUFFIX End
VTrans1: V_SUFFIX
VTrans2: V_SUFFIX
VTrans3: V_SUFFIX
VIntrans: V_SUFFIX
Suffix: End
Comp: End
Adj: End
Be: End
Do: End
VTTrans1: End
VTTrans2: End
VTTrans3: End
VTIntrans: End
WhDet: End
WhIn: End
Wh: End

N_ROOT:
cat N "N[filler -, WhNp -]"
guy N "N[filler -, WhNp -]"
pajama N "N[filler -, WhNp -]"
poirot N "N[filler -, WhNp -]"
solution N "N[filler -, WhNp -]"
police N "N[filler -, WhNp -]"
detective N "N[filler -, WhNp -]"
case N "N[filler -, WhNp -]"
gun N "N[filler -, WhNp -]"
telescope N "N[filler -, WhNp -]"
hill N "N[filler -, WhNp -]"




N_SUFFIX:
+s Suffix ""

PREP:
on End "P"
in End "P"
with End "P"
to End "P"

DET:
the End "Det[filler -]"
a End "Det[filler -]"
an End "Det[filler -]"
some End "Det[filler -]"


TRANSITIVE_1:
solve VTrans1 "VTrans1"
send VTrans1 "VTrans1"
sent End "VTrans1"
lose VTrans1 "VTrans1"
lost End "VTrans1"
see VTrans1 "VTrans1"
saw End "VTrans1"

TTRANSITIVE_1:
see VTTrans1 "I_VTrans1"
lose VTTrans1 "I_VTrans1"
solve VTTrans1 "I_VTrans1"
send VTTrans1 "I_VTrans1"

TRANSITIVE_2:
send VTrans2 "VTrans2"
sent End "VTrans2"

TTRANSITIVE_2:
send VTTrans2 "I_VTrans2"


TTRANSITIVE_3:
believe VTTrans3 "I_VTrans3"


TRANSITIVE_3:
believe VTrans3 "VTrans3"

INTRANSITIVE:
think VIntrans "VIntrans"
thought End "VIntrans"

TINTRANSITIVE:
think VTIntrans "I_VIntrans"

BE:
was End "VState"
were End "VState"
is End "VState"
are End "VState"

COMP:
that Comp "Comp"

AUX:
did Do "DO"

ADJ:
incompetent Adj "Adj"

WHDET:
which WhDet "WhDet[filler +, WhNp +]"

WH:
whom Wh "Wh[filler +, WhNp +]"

WHO:
who WhIn "WhIn[filler -, WhNp -]"

V_SUFFIX:
+ed Suffix ""
+s Suffix ""
'' Suffix ""
+er N ""
'' End None

End:
'#' Begin None

2.3 Discussion of slash feature machinery

Weaknesses: It seems there is not much saving in terms of rules if we are to write explicitly each displaced phrase as we add more rules instead of using fillers e.g.
For each category in the lexicon

*For each rule A -> B C add new rules
A/D -> B C/D and A/D -> B/D C
And as well as: X/X -> [e] (for all X) (slash termination)

That might mean a greater degree of backtracking, i.e. proper branches will be marked iff features are successfully being passed between parents and childs

*Jack Hoeksema- "GPSG, HPSG, LFG"
www.let.rug.nl/~hoeksema/gpsg.ppt

Strengths

The strength of using such a notation is, we allow the sentence to have a gap at arbitrary depths. We attain a free word order by not constraining the order of constituents at all. This might be of great importance in languages that has "free word order"