How do Context Sensitive Grammar systems work?

Question

The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result such as 'aaaaabbbbbccccc'.

What I (think I) understand so far:

• CDG == CSG (context sensitive grammar)
• Linear bounded automata are a form of Turing machine
• Pushdown automata are related in function to a computing stack
• CSG uses linear bounded automata to find and replace portions of text or language
• The above automata result in stacks that should be worked through sort of like code
• Steps in the stack are called productions
• A production is basically a substitution rule
• Productions go opposite the expected direction, pasting the text after the arrow in place of the text before the arrow
• The automata apparently iterate through until the first step is met, and then works through the automata stack until it is done

What I know I do NOT understand:
(I don't expect these questions to be answered - they are only included for detail why I can't seem to solve The Quest)

1. Is the stack iterated over to produce multiple repetitions?

   For example, having some programming experience I expect that to produce a result for The Quest I could start with abc and end with aaaabbbbcccc by creating [if ... then] style statements like:

    a → aa
    b → bb
    c → cc
   

   If starting with {abc} then the above might produce {aabbcc}, iterated again to produce {aaabbbccc}, and again to produce {aaaabbbbcccc}

2. Can production replacements happen while skipping above productions? In the above attempted solution, I would not expect to skip a step or do them out of order, but steps 3 and 4 on the wiki appear to be doing exactly that.

3. Can infinite loops result? In comparing the above example to the wiki example, it would seem to me that completing the first step would cause an infinite loop in which 'a' repeats indefinitely because the first 'a' is converted to 'aa', then the second 'a' that now exists needs the rule to be applied and so on resulting in a → aaaaa∞.

I have been researching for hours, and all searches thus far have resulted in only complicated answers that assume I already have a deep understanding of language processing. I find it ironic that Chomsky's system for describing how language works is apparently so difficult to communicate.

In short, I need programmer syntax to explain how automata stacks should be laid out in order to solve The Quest. Thank you for reading.

Answer 1

Producing sentences from a formal grammar does not require a Linear Bounded Automaton (LBA) and does not use a stack. LBAs are an interesting field of investigation but in terms of this question they are mostly a distraction.

Generative or formal grammars do not actually need much in the way of specialised knowledge to understand, at least in terms of what they do. They are a simple game of symbols, in which you start with a single "start symbol" and then repeatedly apply productions (in any order) until you can no longer find an applicable production. A production is applied by finding its left-hand side in the current string, and replacing that with its right-hand side. That's it.

A formal grammar is slightly more than a set of productions, as the above cited Wikipedia link mentions. It also includes the start symbol, as noted, which precisely defines the starting point, and it also divides symbols into two disjoint sets: terminals and non-terminals. Every production must have at least one non-terminal on its left-hand side, which means that if you reach a string with only terminals, no production can be applied and the replacement sequence terminates. (That's why they are called terminals.) A string containing only terminals is called a "sentence" and the language generated by a grammar is the set of sentences which can be produced.

Strings which are generated which are not sentences -- that is, strings which still contain at least one non-terminal -- are called "sentential forms". Not all sentential forms have an applicable production; such a string is a dead-end.

Grammars are essentially non-deterministic. At every step in the above process (called a "derivation"), there may be a multitude of possible applicable productions, in which case (in theory, at least) all of them are applied in parallel (in parallel universes, that is). This makes it difficult -- actually, impossible -- to know, in general, which sentences can actually be generated by a grammar, but by placing restrictions on the possible productions, we can produce sets of grammars which are more tractable.

One possible restriction is to require that the production's left-hand side "key" non-terminal be surrounded by a prefix and suffix which are also prefix and suffix of the production's right-hand side, which must contain something between the prefix and the suffix. (The prefix and suffix might also contain non-terminals, but unless the production's left-hand and right-hand sides are identical, it's always clear which non-terminal is being replaced by such a rule.) Such a rule is called "context-sensitive" because it conditions the replacement on the context in which the non-terminal symbol appears.

Because the replacement in a context-sensitive rule must contain at least one symbol between the prefix and the suffix, the replaced string must be at least as long as the original, so the derivation must be monotonically non-shrinking. That makes it possible to enumerate the sentences produced by the grammar, using a breadth-first search. In fact, we could use the "non-shrinking" rule as a restriction instead of the context-sensitive restriction; we wouldn't end up with the same set of grammars but we would end up with the same set of possible languages. Because non-shrinking grammars are usually easier to come up with than strictly context-sensitive grammars, some people prefer to use this restriction, even as a definition of what a CSG is. (However, that clouds the meaning of "context".)

An even more drastic restriction is to insist that every left-hand side consist of exactly one non-terminal. Such a grammar is "context-free", because a non-terminal can be replaced regardless of what comes before and after it. Context-free grammars are much easier to deal with; they can be mechanically parsed in somewhat reasonable time (that is, less time than the exponential task of generating all sentences of the correct length and checking if the target sentence is one of them). But many interesting languages, including $a^nb^nc^n$, have no context-free grammar.

Hopefully, that's enough background to understand the example grammar and derivation provided in the Wikipedia article context-sensitive grammars, which shows a grammar which produces $a^nb^nc^n$ and illustrates how $aaabbbccc$ is produced by it. The same process can be used to produce a sentence of any length, simply by iterating rule 2 more often before applying rule 1 and then proceeding to the application of the remaining rules.

Answer 2

Your understanding of Linear Bounded Automata is incorrect. These automata are NOT derived from Pushdown Automata - there is no 'stack' in them. A closer understanding would be that LBA are a special, 'truncated' form of Turing Machine, in which the size of the tape is restricted to being linearly-proportional to the size of the input string (actually, with a large enough alphabet, the tape space can be limited to -just- the space taken by the input string).

Also, the grammar-expansion behavior described in (1) is more closely analogous to a Lindenmyer System, which is not quite the same as a CSG (in which only one substitution takes place at any one step, so (3) isn't a concern).