Grammar for language L = {ww ∣ w ∈ {a,b,c} * }

Question

I am new to linguistics and trying to understand how to construct a grammar. I am however having issues on this.

L= {ww ∣ w ∈ {a,b,c} ^∗ }

is a linear indexed language, how can I construct the grammar for this language?

Answer 1

Despite not being so hot when it comes to formal language theory, i decided to take a stab at an answer after all (using this as a reference). Here is the grammar for the language L = {ww ∣ w ∈ {a,b,c} ∗ }, which consists of a set of rewrite rules:

S[x] -> S[xf] | S[xg] | S[xh]
S[x] -> T[x]T[x]
T[xf] -> T[x]a
T[xg] -> T[x]b
T[xh] -> T[x]c
T[] -> E

Where: x denotes an arbitrary collection of stack symbols, S is the sentence symbol, T, f, g and h are non-terminals, a,b and c are terminals, and E is the empty string.

The derivation of the string aabbccaabbcc is as follows:

S[] -> S[f] -> S[ff] -> S[ffg] -> S[ffgg] -> S[ffggh] -> S[ffgghh] -> T[ffgghh]T[ffgghh] > -> T[ffggh]cT[ffgghh] -> T[ffgg]ccT[ffgghh]-> T[ffg]bccT[ffgghh] -> T[ff]bbccT[ffgghh] > -> .. -> T[]aabbccT[ffgghh] -> aabbccT[ffgghh] -> ... -> aabbccaabbcc

As desired, the grammar only generates strings ww (w concatenated with itself), where w is an arbitrarily long sequence of a, b and c in any order.

A small explanatory note:

This grammar works crucially by defining the copying rule S[x] -> T[x]T[x]. This rewrite rule takes the stack of symbols on S, and duplicates the stack on two new non-terminals, which exist only to hold the duplicated stacks (they are ultimately deleted via T[] -> E). Once the stacks have been duplicated, the non-terminals in the stacks are 'popped off' one by one to generate strings of terminals. Because the stacks have previously been duplicated, the strings resulting from popping off non-terminals from the stacks of T are guaranteed to be identical.