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)
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}
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.
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.
CDG
come from? $\endgroup$