SkipCaptcha
265
edits
Changes
→Level 0: recursively enumerable grammar: add example
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:
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]
*[anything] -> [anything]
====Example====
The following rules can generate all symbols of the form: abc, aabbcc, aaabbbccc, etc., where there are equal numbers of a's, b's and c's. This example is taken from a lecture.<ref>{{cite web
| url = http://www.cs.utexas.edu/~cline/ear/Slides/Turing/TuringSlides3.doc
| title = Grammars, Recursively Enumerable Languages, and Turing Machines
| accessdate = 2012-05-10
}}</ref>
''S'' -> '''a''' ''B'' ''S'' '''c'''
''S'' -> '''a''' ''B'' '''c'''
''B'' '''a''' -> '''a''' ''B''
''B'' '''c''' -> '''b''' '''c'''
''B'' '''b''' -> '''b''' '''b'''
The derivations of the first three items in this infinite sequence are:
# ''S'' -> '''a'''''B'''''c''' -> '''abc'''
# ''S'' -> '''a'''''BS'''''c''' -> '''a'''''B'''''a'''''B'''''cc''' -> '''aa'''''B B'''''cc''' -> '''aa'''''B'''''bcc''' -> '''aabbcc'''
# ''S'' -> '''a'''''BS'''''c''' -> '''a'''''B'''''a'''''BS'''''cc''' -> '''a'''''B'''''a'''''B'''''a'''''B'''''ccc''' -> '''aa'''''BB'''''a'''''B'''''ccc''' -> '''aa'''''B'''''a'''''BB'''''ccc''' -> '''aaa'''''BBB'''''ccc''' -> '''aaa'''''BB'''''bccc''' -> '''aaa'''''B'''''bbccc''' -> '''aaabbbccc'''
===Beyond Level 0===
===Beyond Level 0===