SkipCaptcha
265
edits
Changes
→Chomsky hierarchy: regular grammar for a ''Word''
The descriptions of the various Chomsky levels which follows is presented in reverse order, so as to work up from a simple case to a rather complicated case.
The descriptions of the various Chomsky levels which follows is presented in reverse order, so as to work up from a simple case to a rather complicated case.
===Level 3===
===Level 3: regular grammar===
In its simplest form a ''Word'' consists of a sequence of one or more letters. In the regular grammar which follows the two possible transformations of ''PartWord'' are placed on separate lines instead of on one line separated by a comma. We ignore capital letters for now. ''PartWord'' is recursively defined and may be transformed into nothing.
''Word'' -> ''Letter'' ''PartWord''
''PartWord'' -> [nothing]
''PartWord'' -> ''Letter'' ''PartWord''
''Letter'' -> '''a''', '''b''', ... '''z'''
For one-letter words we expand as:
:''Word'' -> ''Letter'' ''PartWord'' -> ''Letter'' [nothing] -> ''Letter''
For two-letter words we expand as:
:''Word'' -> ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' [nothing] -> ''Letter'' ''Letter''
===Level 2===
===Level 2===