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

Related articles
Question re the (non-)equivalence of Z -> z and Z -> z e (e the empty dhalitsky@cumulativeinquiry.com (2004-08-09)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em kwheinri@bsr2.uwaterloo.ca (Kenn Heinrich) (2004-08-10)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em k301x@yahoo.com (dtf) (2004-08-10)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em dhalitsky@cumulativeinquiry.com (2004-08-11)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em cppljevans@cox-internet.com (Larry Evans) (2004-08-11)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em kwheinri@bsr2.uwaterloo.ca (Kenn Heinrich) (2004-08-13)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em dhalitsky@cumulativeinquiry.com (2004-08-13)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em parsersinc@earthlink.net (SLK Parsers) (2004-08-15)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em dhalitsky@cumulativeinquiry.com (2004-08-23)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em parsersinc@earthlink.net (SLK Parsers) (2004-09-03)
| 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.