Context Sensitive Grammar (Automata theory)


by Dafydd
Tags: automata, context, grammar, sensitive, theory
Dafydd
Dafydd is offline
#1
Aug4-10, 09:41 AM
P: 12
Sorry if this is the wrong forum.

I'm trying to get my head around Context Sensitive Grammar. In my coursebook, there's an example ('e' here is the empty string, epsilon, and 'E' is the "set member" symbol):

The language {an bn cn | n E N} is described by the following rules:

S -> e | abNSc
bNa -> abN
bNb -> bbN
bNc -> bc

And then it shows how to build aabbcc:

S -> abNSc
-> abNabNScc
-> abNabNcc
-> aabNbcc
-> aabbNcc
-> aabbcc

The part I don't understand is why S becomes abNSc after the first substitution, while the second time it becomes an empty string. The rules state both substitutions are possible, but not when to use which one. Can this be choosen freely?

Another language (with 4 non-deterministic symbols S, D, [, ]) describes {1, 1^2, 1^4, 1^8, ...}. Its rules:

S -> [1]
[ -> [D
D1 -> 11D
D] -> ]
[ -> e
] -> e

Example, building the string 11111111:

S -> [1] -> [D1] ->* [DDD1]
-> [DD1D]
-> [D11D1D]
-> [D1111DD]
-> [11D111DD]
-> [1111D11DD]
-> [111111D1DD]
-> [11111111DDD]
-> [11111111DD]
-> [11111111D]
-> [11111111]
-> [11111111
-> 11111111

Again, the number of times a substitution is carried out seems to be random, or at least arbitrary. Why do you not just keep doing the substitution from [ to [D indefinitely? Because you know how many times it needs to be done in order to get the resulting string you want? Can you choose to do the substitutions in any order you want (as long as it gets you the result you want), or is there a pattern to follow?

Thanks for any help.
Phys.Org News Partner Science news on Phys.org
Internet co-creator Cerf debunks 'myth' that US runs it
Astronomical forensics uncover planetary disks in Hubble archive
Solar-powered two-seat Sunseeker airplane has progress report
Hurkyl
Hurkyl is offline
#2
Aug4-10, 10:15 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
The language defined by a grammar consists of every string that you can produce by applying the production rules.
Can you choose to do the substitutions in any order you want
So yeah.
Dafydd
Dafydd is offline
#3
Aug4-10, 10:22 AM
P: 12
That's all I needed to hear. Thank you!


Register to reply

Related Discussions
List of numbers, context-sensitive? General Math 0
Theory of computation, automata, machines Other Science Learning Materials 0
Context Free Grammar Engineering, Comp Sci, & Technology Homework 0
Point of automata theory in ECE? Academic Guidance 1
context-free grammar: derivations and ambiguity Programming & Computer Science 2