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

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.

Return to the comp.compilers page.
Search the comp.compilers archives again.