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

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

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