SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 263:
Line 263: − + − X [non-terminal] Y -> X [anything] Y Line 307:
Line 306: − + − + − [anything] -> [anything] Line 318:
Line 316: − +
→Chomsky hierarchy: make notation consistent. note re 'beyond level 0'
There is only one transformation rule for context-sensitive grammars:
There is only one transformation rule for context-sensitive grammars:
*X [non-terminal] Y -> X [anything] Y
where X and Y determine the context in which the [non-terminal] is transformed. Note that X and Y may each be terminals or non-terminals or [nothing]. When both X and Y are nothing there is no context and this reduces to a Level 2 or Level 3 grammar.
where X and Y determine the context in which the [non-terminal] is transformed. Note that X and Y may each be terminals or non-terminals or [nothing]. When both X and Y are nothing there is no context and this reduces to a Level 2 or Level 3 grammar.
===Level 0: recursively enumerable grammar===
===Level 0: recursively enumerable grammar===
A recursively enumerable grammar has absolutely no restriction on what sort of transformation rules can be applied. Rules take the general form:
A recursively enumerable grammar has absolutely no restriction on what sort of transformation rules can be applied; hence it is also known as an unrestricted grammar. Rules take the general form:
*[anything] -> [anything]
===Beyond Level 0===
===Beyond Level 0===
| accessdate = 2012-05-05
| accessdate = 2012-05-05
}}</ref>
}}</ref>
show that languages exist which can not be described by any set of rules.
show that languages exist which can not be described by any set of rules. As is common with logical proofs of this nature, the proof doesn't actually produce or demonstrate such a language.
==References==
==References==