# Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the empty string)

## dhalitsky@cumulativeinquiry.com (David Halitsky)

11 Aug 2004 12:56:36 -0400

*From comp.compilers*

| List of all articles for this month |

**From: ** | dhalitsky@cumulativeinquiry.com (David Halitsky) |

**Newsgroups: ** | comp.compilers |

**Date: ** | 11 Aug 2004 12:56:36 -0400 |

**Organization: ** | http://groups.google.com |

**References: ** | 04-08-046 04-08-058 |

**Keywords: ** | parse, theory, summary |

I am grateful to KH for his lucid and simple explanation concerning

the difference between considering 'e' as an element of Vt and

considering 'e' as present in strings which are otherwise exclusively

over Vt.

If Robert Low is corrrect in his observation that a right linear

grammar is still linear even if its last possible production intoduces

two terminals while all possible prior productions introduce just one

(see thread at sci.math, sci.logic, or comp.theory entitled "Z -> z vs

Z -> z e"), then it is not necessary for me to use a production of the

form "Z -> z e" in order to construct the argument I'm leading up to

(in that thread.)

But even though the wrong-headed "Z -> z e" is no longer needed, I am

nonetheless grateful to KH for pointing out its wrong-headedness in a

way which has not been done by responders at sci.math, sci.logic, nor

comp.theory.

PS - much of Chomsky's later applied work relies critically on several

different types of empty symbols which would have to be regarded as

elements of Vt if they were to be formalized. But since C and some of

his key students have moved entirely away from formalisms as being

premature for applied linguistics, these "applied" empty symbols are

not sufficiently well-defined to contradict your point concerning 'e'

in the context of a formal theory of language/ automata.

Thanks very much again.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.