9 Aug 2004 01:30:03 -0400

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) |

[3 later articles] |

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

Newsgroups: | comp.compilers |

Date: | 9 Aug 2004 01:30:03 -0400 |

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

Keywords: | parse, theory, question |

Posted-Date: | 09 Aug 2004 01:30:03 EDT |

Background

Consider any linear grammar G of a regular language L in which:

a) the designated "empty" or "null string" symbol e is not an

element of G's terminal alphabet Vt;

b) G contains the rewrite rule Z -> z, which always terminates a

derivation in G since z is an element of Vt;

Now consider a grammar G' of a regular language L which is just

like G except that:

a) the terminal alphabet Vt' of G' does contain the null/empty string

symbol e

b) G' contains the rewrite rule Z -> z e instead of Z -> z.

In any derivation D in G, the deepest subtree in D will be a tree

consisting of one parent with one child:

[ z ]

Z

In the corresponding derivation D' in G', the deepest subtree will be

a tree consisting of one parent and two children:

[ z e ]

Z

Question

Can anyone think of any non-trivial reason why the grammars G and G'

should be distinguished one from the other within formal language

theory or automata theory or any application thereof ?

The answer to this question has both formal and empirical

consequences, otherwise I would not be wasting anyone's time to

double-check my own opinion on the matter.

Thanks for whatever time you can afford to spend considering this

matter.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.