Re: [stack] Is this language concatenative?

Very nice counter-example!
Any ideas on how to refine the definition?

-Christopher


On 4/29/07, Michael Nedzelsky <[email protected]> wrote:
>
>   Hi!
>
> Consider the following example. Is this language concatenative?
>
> The set of terminal symbols T = { 'a', '(', ')' }.
>
> The grammar G_0 has the following production rules:
> S -> e # empty string
> S -> S S
> S -> ( S1 )
> S1 -> a | a S1
>
> The grammar G_0 generates the language L \subset T*.
> Some elements of L are
> e, (a), (a)(aa), (aaa)(a), etc.
>
> We have LL = L, i.e. the concatenation of two elements of L belongs to L.
>
> It seems to me that L is a concatenative language, but it doesn't satisfy
> the Christopher's definition (there is no concatenative grammar which
> generates this language - the proof is a simple exercise).
>
> What do you think?
>
> Michael Nedzelsky
>
> 
>


[Non-text portions of this message have been removed]