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?

  • I'm not actually so clear on how to interpret the formalism here. Should it be read like this? : "L is the set of strings derived by concatening a string w with itself, where w is a sequence of either a, b, or c of arbitrary length".
    – P Elliott
    Jan 25, 2014 at 18:55
  • You are absolutely right. a,b,c can be in any order and any length. Jan 25, 2014 at 18:59
  • 1
    Ok, so an example of a string which would count as a member of L would be aabcccaabccc? and likewise abcaabbcc wouldn't?
    – P Elliott
    Jan 25, 2014 at 19:02
  • 1
    Would this not be a better fit for Computer Science?
    – Raphael
    Jan 26, 2014 at 14:22
  • 1
    @Raphael I personally welcome questions about grammar formalisms here on linguistics SE, although i can't speak for everyone.
    – P Elliott
    Jan 26, 2014 at 15:01

1 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.

  • If you're going to downvote my answer i'd appreciate it if you'd point out where you think i've gone wrong. I'm reasonably confident that this is the grammar for the language defined in the question, so i can't see what the problem is without an explanation.
    – P Elliott
    Jan 26, 2014 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.