10 Aug 2004 17:35:06 -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) |

Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em parsersinc@earthlink.net (SLK Parsers) (2004-08-15) |

[2 later articles] |

From: | Kenn Heinrich <kwheinri@bsr2.uwaterloo.ca> |

Newsgroups: | comp.compilers |

Date: | 10 Aug 2004 17:35:06 -0400 |

Organization: | University of Waterloo |

References: | 04-08-046 |

Keywords: | parse, theory |

Posted-Date: | 10 Aug 2004 17:35:06 EDT |

dhalitsky@cumulativeinquiry.com (David Halitsky) writes:

*> 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.*

*>*

... snip...

*> 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 ?*

*>*

David,

I'd argue with your use of e. In automata theory, e is not usually

interpreted as a symbol in the alphabet Vt. Rather, it's the identity

element you add to Vt+ (the free semigroup over Vt) to get Vt* (free

monoid). So by definition, (x e) = (x). e may be a string in a

language L which is a subset of Vt* but is not an element of Vt.

If you were to try to think of e as an element of Vt' = Vt + e which

behaved as though it were an identity for Vt'*, there would be an

obvious morphism from strings in Vt'* to Vt* which just erases the

e's, so you would see the same language over Vt*. The only way to

extend this morphism to actions is to make the grammar action on e be

the identity action as well (i.e. no action associated with the e in

any production ).

The problem that comes in is that you introduce nondeterminism if you

try to associate any sort of action with e. Then, since ee = e = e* =

e^k, you have ambiguity. If you tried to stretch the notation even

further and had a production Y ::= e y generating another language,

you could probably concoct some trouble composing the languages L1L2.

Hope this helps... I'm more familiar with automata than grammar,

though.

- Kenn

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.