Minimalist Machine Derivations

Files: grammar.pl / m12.pl / Back to homepage

Examples:

Test cases from A Course in GB Syntax (Lasnik & Uriagereka,1988). collapse

Example	Instruction stream (clickable)	Notes
Strong Crossover
Who₁ thinks (that) Mary likes him₁	[who, q, he, d, like, 'v*', [mary, d], 'T', c_eQ, think, v_unerg, 'T', c_Q]	Doubling Constituent (DC) he-who object of embedded verb like. Two derivations. [Note: Need to allow c stack search to find (inactive) who.]
Who₁ thinks (that) Mary likes him₂	[he, d, like, 'v*', [mary, d], 'T', c_e, think, v_unerg, [who, q], 'T', c_Q]	No DC. He is object of embedded verb like. Who is subject of matrix verb think. Two derivations.
*Who₁ does he₁ think Mary likes		No DC analysis possible.
Who₁ does he₂ think (that) Mary likes	[who, q, like, 'v*', [mary, d], 'T', c_eQ, think, v_unerg, [he, d], 'T', c_Q]	No DC. Who object of embedded verb like. He subject of matrix verb think. Two derivations.

Parameter	Setting	Description
substream_stack	on	Allow transfer of substream stack back to mainstream
stack_update_larger	off	Replace updated subconstituent of stack element
pmerge_flag	off	Allow spellout of pair-merge in either order
inactive_push	on	Push nonhead of DC merge onto the stack inactive(_)
search	stk	Search SO or stack for unvalued uF to be released
drop_stack	off	Drop stack items that are two phase boundaries down
stack_access	local	Local or global access to elements of the stack
le	on	Local Extent boundary conditions, used to trigger stacking of unvalued uF SOs
subphrase_check	subsume_ss	Push element onto stack, first check if subconstituent is already there
c_stack_search	inactive	c stack search normal or can see into inactive wrapped elements
occ_new_flag	off	if already old, create new, otherwise keep old
stack_subc	off	if existing subconstituent found on stack, mark old and substitute new on stack
vprint	on	Print stack as vertical list
occ_debug	off	use @ to indicate occ(V), V a variable

Machine Parameters: expand

Animation:
Who₁ thinks (that) Mary likes him₂

Derivation:
Who₁ thinks (that) Mary likes him₂

Stream:	[[he!D],[d!case!N],[like],[v*!phi],[[mary!D],[d!case!N]],[T!phi],[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):
SO:	[]

Step 1.

Head of stream [he!D] is the initial SO

Stream:	[[d!case!N],[like],[v*!phi],[[mary!D],[d!case!N]],[T!phi],[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):
SO:	[he!D]

Step 2.

Merge [d!case!N] and [he!D]

Label from [d!case!N] (head with an unvalued uF)

Inherit interpretable feature(s) [f(phi,[3,sg,m])] from [he!D]

[d!case!N] values D on [he!D]

[he] values N on [d!case!N]

Stream:	[[like],[v*!phi],[[mary!D],[d!case!N]],[T!phi],[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):
SO:	[d!case[d][he]]

Step 3.

Merge [like] and [d!case[d][he]]

Label from [like] (head merging with a non-head)

Theta-mark [d!case[d][he]]

Push [d!case[d][he]] (unvalued uF) onto stack

Stream:	[[v*!phi],[[mary!D],[d!case!N]],[T!phi],[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d!case[d][he]]
SO:	[like[like][d!case[d][he]]]

Step 4.

Merge [v*!phi] and [like[like][d!case[d..][he..]]]

Label from [v*!phi] (head merging with a non-head)

[d!case[d][he]] values uPhi on [v*!phi]

[v*] values acc case on [d!case[d][he]]

Stream:	[[[mary!D],[d!case!N]],[T!phi],[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d[d][he]]
SO:	[v[v][like[like][d[d][he]]]]

Step 5.

Begin substream

Stream:	[[mary!D],[d!case!N]]
Stack (⥥):
SO:	[]

Step 6.

Head of stream [mary!D] is the initial SO

Stream:	[[d!case!N]]
Stack (⥥):
SO:	[mary!D]

Step 7.

Merge [d!case!N] and [mary!D]

Label from [d!case!N] (head with an unvalued uF)

Inherit interpretable feature(s) [f(phi,[3,sg,n])] from [mary!D]

[d!case!N] values D on [mary!D]

[mary] values N on [d!case!N]

Stream:	[]
Stack (⥥):
SO:	[d!case[d][mary]]

End substream, SO [d!case[d][mary]] re-inserted into main stream

Step 8.

Stream:	[[d!case[d][mary]],[T!phi],[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d[d][he]]
SO:	[v[v][like[like][d[d][he]]]]

Step 9.

Merge [v*[v*][like[like..][d..]]] and [d!case[d][mary]]

Label from [v*[v*][like[like..][d..]]] (edge feature)

Theta-mark [d!case[d][mary]]

Push [d!case[d][mary]] (unvalued uF) onto stack

Stream:	[[T!phi],[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d!case[d][mary]] [d[d][he]]
SO:	[v[d!case[d][mary]][v[v*][like[like][d[d][he]]]]]

Step 10.

Merge [T!phi] and [v*[d!case[d..][mary..]][v*[v*..][like..]]]

Label from [T!phi] (head merging with a non-head)

[d!case[d][mary]] values uPhi on [T!phi]

[T] values nom case on [d!case[d][mary]]

Stream:	[[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d[d][mary]] [d[d][he]]
SO:	[T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]

Step 11.

Internal merge selected

Merge [T[T][v*[d..][v*..]]] and [d[d][mary]]

Label from [T[T][v*[d..][v*..]]] (edge feature)

Stream:	[[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d[d][mary]] [d[d][he]]
SO:	[T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]

Step 12.

Merge [c_e!T] and [T[d[d..][mary..]][T[T..][v*..]]]

Label from [c_e!T] (head merging with a non-head)

[d[d][mary]] values T on [c_e!T]

Internal merge selected

Merge [c_e[c_e][T[d..][T..]]] and [d[d][mary]]

Label from [c_e[c_e][T[d..][T..]]] (edge feature)

Stream:	[[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d[d][mary]] [d[d][he]]
SO:	[c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]

Step 13.

Local Extent boundary at [c_e[d[d..][mary..]][c_e[c_e..][T..]]]

New boundary (b) marker stacked

Stream:	[[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]

Step 14.

Merge [think] and [c_e[d[d..][mary..]][c_e[c_e..][T..]]]

Label from [think] (head merging with a non-head)

Theta-mark [c_e[d[d..][mary..]][c_e[c_e..][T..]]]

Stream:	[[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]

Step 15.

Merge [v_unerg] and [think[think][c_e[d..][c_e..]]]

Label from [v_unerg] (head merging with a non-head)

Stream:	[[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[v_unerg[v_unerg][think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]

Step 16.

Begin substream

Stream:	[[who!D],[q!case!N!scope]]
Stack (⥥):
SO:	[]

Step 17.

Head of stream [who!D] is the initial SO

Stream:	[[q!case!N!scope]]
Stack (⥥):
SO:	[who!D]

Step 18.

Merge [q!case!N!scope] and [who!D]

Label from [q!case!N!scope] (head with an unvalued uF)

Inherit interpretable feature(s) [f(phi,[3,sg,n])] from [who!D]

[q!case!N!scope] values D on [who!D]

[who] values N on [q!case!N!scope]

Stream:	[]
Stack (⥥):
SO:	[q!case!scope[q!scope][who]]

End substream, SO [q!case!scope[q!scope][who]] re-inserted into main stream

Step 19.

Stream:	[[q!case!scope[q!scope][who]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[v_unerg[v_unerg][think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]

Step 20.

Merge [v_unerg[v_unerg][think[think..][c_e..]]] and [q!case!scope[q!scope][who]]

Label from [v_unerg[v_unerg][think[think..][c_e..]]] (edge feature)

Theta-mark [q!case!scope[q!scope][who]]

Push [q!case!scope[q!scope][who]] (unvalued uF) onto stack

Stream:	[[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[q!case!scope[q!scope][who]] b [d[d][mary]] [d[d][he]]
SO:	[v_unerg[q!case!scope[q!scope][who]][v_unerg[v_unerg][think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]

Step 21.

Merge [T!phi!v] and [v_unerg[q!case!scope[q..][who..]][v_unerg[v_unerg..][think..]]]

Label from [T!phi!v] (head merging with a non-head)

[q!case!scope[q!scope][who]] values uPhi on [T!phi!v]

[T!v] values nom case on [q!case!scope[q!scope][who]]

Relativized TOS search for iF(v) skipping [q!scope[q!scope][who]]

[T!v] attracts [v_unerg[q!scope[q..][who..]][v_unerg[v_unerg..][think..]]]

Merge [T[T][v_unerg[q..][v_unerg..]]] and [v_unerg]

Label from [T[T][v_unerg[q..][v_unerg..]]] (edge feature)

Stream:	[[c_Q!wh!T]]
Stack (⥥):	[q!scope[q!scope][who]] b [d[d][mary]] [d[d][he]]
SO:	[T[v_unerg][T[T][v_unerg[q!scope[q!scope][who]][v_unerg[v_unerg][think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]

Step 22.

Internal merge selected

Merge [T[v_unerg][T[T..][v_unerg..]]] and [q!scope[q!scope][who]]

Label from [T[v_unerg][T[T..][v_unerg..]]] (edge feature)

Stream:	[[c_Q!wh!T]]
Stack (⥥):	[q!scope[q!scope][who]] b [d[d][mary]] [d[d][he]]
SO:	[T[q!scope[q!scope][who]][T[v_unerg][T[T][v_unerg[q!scope[q!scope][who]][v_unerg[v_unerg][think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]]

Step 23.

Merge [c_Q!wh!T] and [T[q!scope[q..][who..]][T[v_unerg..][T..]]]

Label from [c_Q!wh!T] (head merging with a non-head)

[q!scope[q!scope][who]] values wh on [c_Q!wh!T]

[q!scope[q!scope][who]] values T on [c_Q!T] (economy)

Internal merge selected

[c_Q] values uscope on [q!scope[q!scope][who]]

Merge [c_Q[c_Q][T[q..][T..]]] and [q[q][who]]

Label from [c_Q[c_Q][T[q..][T..]]] (edge feature)

Stream:	[]
Stack (⥥):	[q[q][who]] b [d[d][mary]] [d[d][he]]
SO:	[c_Q[q[q][who]][c_Q[c_Q][T[q[q][who]][T[v_unerg][T[T][v_unerg[q[q][who]][v_unerg[v_unerg][think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]]]]

Step 24.

Local Extent boundary at [c_Q[q[q..][who..]][c_Q[c_Q..][T..]]]

New boundary (b) marker stacked

Stream:	[]
Stack (⥥):	b [q[q][who]] b [d[d][mary]] [d[d][he]]
SO:	[c_Q[q[q][who]][c_Q[c_Q][T[q[q][who]][T[v_unerg][T[T][v_unerg[q[q][who]][v_unerg[v_unerg][think[think][c_e[d[d][mary]][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]]]]

CI: wh-question

Parse:

Spell-out:

who -s think mary -s like -acc he (after morpheme realization)

who think -s mary like -s he -acc (after affix-hop)

who think -s mary like -s he -acc (after morpheme realization, stage 2)

who thinks mary likes him

Backtrack

Stream:	[[c_e!T],[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d[d][mary]] [d[d][he]]
SO:	[T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]

re-doing step 12

Step 25.

[c_e!T] attracts [T[d[d..][mary..]][T[T..][v*..]]]

Internal merge selected

Merge [c_e[c_e][T[d..][T..]]] and [T]

Label from [c_e[c_e][T[d..][T..]]] (edge feature)

Stream:	[[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[d[d][mary]] [d[d][he]]
SO:	[c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]

Step 26.

Local Extent boundary at [c_e[T][c_e[c_e..][T..]]]

New boundary (b) marker stacked

Stream:	[[think],[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]

Step 27.

Merge [think] and [c_e[T][c_e[c_e..][T..]]]

Label from [think] (head merging with a non-head)

Theta-mark [c_e[T][c_e[c_e..][T..]]]

Stream:	[[v_unerg],[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]

Step 28.

Merge [v_unerg] and [think[think][c_e[T..][c_e..]]]

Label from [v_unerg] (head merging with a non-head)

Stream:	[[[who!D],[q!case!N!scope]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[v_unerg[v_unerg][think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]

Step 29.

Begin substream

Stream:	[[who!D],[q!case!N!scope]]
Stack (⥥):
SO:	[]

Step 30.

Head of stream [who!D] is the initial SO

Stream:	[[q!case!N!scope]]
Stack (⥥):
SO:	[who!D]

Step 31.

Merge [q!case!N!scope] and [who!D]

Label from [q!case!N!scope] (head with an unvalued uF)

Inherit interpretable feature(s) [f(phi,[3,sg,n])] from [who!D]

[q!case!N!scope] values D on [who!D]

[who] values N on [q!case!N!scope]

Stream:	[]
Stack (⥥):
SO:	[q!case!scope[q!scope][who]]

End substream, SO [q!case!scope[q!scope][who]] re-inserted into main stream

Step 32.

Stream:	[[q!case!scope[q!scope][who]],[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	b [d[d][mary]] [d[d][he]]
SO:	[v_unerg[v_unerg][think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]

Step 33.

Merge [v_unerg[v_unerg][think[think..][c_e..]]] and [q!case!scope[q!scope][who]]

Label from [v_unerg[v_unerg][think[think..][c_e..]]] (edge feature)

Theta-mark [q!case!scope[q!scope][who]]

Push [q!case!scope[q!scope][who]] (unvalued uF) onto stack

Stream:	[[T!phi!v],[c_Q!wh!T]]
Stack (⥥):	[q!case!scope[q!scope][who]] b [d[d][mary]] [d[d][he]]
SO:	[v_unerg[q!case!scope[q!scope][who]][v_unerg[v_unerg][think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]

Step 34.

Merge [T!phi!v] and [v_unerg[q!case!scope[q..][who..]][v_unerg[v_unerg..][think..]]]

Label from [T!phi!v] (head merging with a non-head)

[q!case!scope[q!scope][who]] values uPhi on [T!phi!v]

[T!v] values nom case on [q!case!scope[q!scope][who]]

Relativized TOS search for iF(v) skipping [q!scope[q!scope][who]]

[T!v] attracts [v_unerg[q!scope[q..][who..]][v_unerg[v_unerg..][think..]]]

Merge [T[T][v_unerg[q..][v_unerg..]]] and [v_unerg]

Label from [T[T][v_unerg[q..][v_unerg..]]] (edge feature)

Stream:	[[c_Q!wh!T]]
Stack (⥥):	[q!scope[q!scope][who]] b [d[d][mary]] [d[d][he]]
SO:	[T[v_unerg][T[T][v_unerg[q!scope[q!scope][who]][v_unerg[v_unerg][think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]

Step 35.

Internal merge selected

Merge [T[v_unerg][T[T..][v_unerg..]]] and [q!scope[q!scope][who]]

Label from [T[v_unerg][T[T..][v_unerg..]]] (edge feature)

Stream:	[[c_Q!wh!T]]
Stack (⥥):	[q!scope[q!scope][who]] b [d[d][mary]] [d[d][he]]
SO:	[T[q!scope[q!scope][who]][T[v_unerg][T[T][v_unerg[q!scope[q!scope][who]][v_unerg[v_unerg][think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]]

Step 36.

Merge [c_Q!wh!T] and [T[q!scope[q..][who..]][T[v_unerg..][T..]]]

Label from [c_Q!wh!T] (head merging with a non-head)

[q!scope[q!scope][who]] values wh on [c_Q!wh!T]

[q!scope[q!scope][who]] values T on [c_Q!T] (economy)

Internal merge selected

[c_Q] values uscope on [q!scope[q!scope][who]]

Merge [c_Q[c_Q][T[q..][T..]]] and [q[q][who]]

Label from [c_Q[c_Q][T[q..][T..]]] (edge feature)

Stream:	[]
Stack (⥥):	[q[q][who]] b [d[d][mary]] [d[d][he]]
SO:	[c_Q[q[q][who]][c_Q[c_Q][T[q[q][who]][T[v_unerg][T[T][v_unerg[q[q][who]][v_unerg[v_unerg][think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]]]]

Step 37.

Local Extent boundary at [c_Q[q[q..][who..]][c_Q[c_Q..][T..]]]

New boundary (b) marker stacked

Stream:	[]
Stack (⥥):	b [q[q][who]] b [d[d][mary]] [d[d][he]]
SO:	[c_Q[q[q][who]][c_Q[c_Q][T[q[q][who]][T[v_unerg][T[T][v_unerg[q[q][who]][v_unerg[v_unerg][think[think][c_e[T][c_e[c_e][T[d[d][mary]][T[T][v[d[d][mary]][v[v*][like[like][d[d][he]]]]]]]]]]]]]]]]]

CI: wh-question

Parse:

Spell-out:

who -s think that mary -s like -acc he (after morpheme realization)

who think -s that mary like -s he -acc (after affix-hop)

who think -s that mary like -s he -acc (after morpheme realization, stage 2)

who thinks that mary likes him

2 derivations found.

Computational Cost:

Merge: 28, Agree: 24, Unify: 0, Push: 4, Boundaries: 4, Inject: 0

Non-TOS access: 2, Pop: 0, Depth cost: 53

Step:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37
Stack depth:	0	0	0	1	1	0	0	0	1	2	2	2	2	3	3	3	0	0	0	3	4	4	4	4	5	2	3	3	3	0	0	0	3	4	4	4	4	5