Re: Extended context-free grammar

David Wagner <daw@xxxxxxxxxxxxxxxxxxxxxxxx> wrote:
This is a very interesting approach, one I hadn't considered.
But, it doesn't look like it is guaranteed to terminate. For
example, if the original grammar is
S ::= x' T A
T ::= x U B
U ::= x' T
then it looks like we get into an infinite loop, if I understand
your transformation rules correctly. First we add the production
S ::= x' T B A
then we add the production
S ::= x' T B B A
and then
S ::= x' T B B B A
and so on ad infinitum. It may be that this kind of case can be
detected and avoided; I don't know yet.

Ok, here's a different idea: If a production S ::= x \ T is going
to actually produce anything, it will have to produce a prefix

x'_1 x'_2 ... x'_n x_n ... x_2 x_1 y ...

after introduction of "special" terminals (but before transformation).

Now, similar to the the pumping lemma, there should be a smallest such
prefix sequence (otherwise there's a "loop" in the derivation which
can be eleminated). So the length of this prefix sequence is bounded,
and the bound is the same for every rule. With this information,
one should be able to work out a bound on the number of substitutions
of the kind given above, before one can give up because the rule
isn't going to produce a concrete word (note that the grammar given
above doesn't produce one, either).

You also may have to think about whether the definition

S ::= x \ T produces a word w iff T produces x.w

is well-defined in the first place, because it may be recursive, and
(at least to me) it's not obvious how to resolve that. E.g., consider

S ::= x \ T
T ::= x S U
U ::= \epsilon | y

Does this grammar produce anything?

- Dirk

.

Relevant Pages