Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?


Right. According Aho&Ullman CSG is defined with the only restriction
on the lengths of the words on the LHS and the RHS of the rule:

alpha <- beta

|alpha| <= |beta|

Therefore, even ab=ba is a valid rule in Aho&Ullman sense. Then,
exercise 2.1.5 introduces "true" CSG (e.g. as defined on wikipedia
page) and suggests that there is no loss of generality.

In fact, there is no need to change definition. Simply convert

AB = BA

to three context-sensitive production rules:

AB = AX
AX = YX
YX = YA
YA = BA


--
Lech
.

Relevant Pages

  • I forget the Induction Joke ...
    ... Drama in one act with 4 characters: The Grand Alpha, The Grand Beta, ... The Grand Omicron, and The Candidate. ... Please define a compact set. ...
    (rec.org.mensa)
  • Re:Re: Alpha, beta, ....
    ... Firefox 3 was done at alpha 3 (when i never hit a bug again and it pa? ... hanges to beta 1. ... I for one was happy to see Firefox 3 as in 7.10, ... There must be a different than gnash tool to play swf as I don't have gnash? ...
    (Ubuntu)
  • Re: The Dangerous Liberty of Engineering vs. Lukewarm Dominionism
    ... with alpha, beta, and gamma also part of a smooth mani- ... violates CPT invariance, ...
    (sci.space.policy)
  • Re: Accessing an invoking classs getters?
    ... >> from Alpha to Beta, even a fairly long list of values, ... > If there's no other relation between an instance of an Alpha and a Beta, ... > this would be the prefered method, as you then decouple the dependence to ... should probably be called AlphaPreferences, ...
    (comp.lang.java.programmer)
  • Re: interpolation theorem of propositional logic
    ... beta. ... Depends on what one understands by sentence symbols. ... from propositional variables to propositional ...
    (sci.logic)