SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 158:
Line 158: − + + + Line 169:
Line 171: − + + + + + + +
→Level 3: regular grammar: limitations
===Level 3: regular grammar===
===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.
This example of a regular grammar shows how a ''Word'' can be defined as a sequence of ''Letter''s.
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''
''Word'' -> ''Letter'' ''PartWord''
For two-letter words we expand as:
For two-letter words we expand as:
:''Word'' -> ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' [nothing] -> ''Letter'' ''Letter''
:''Word'' -> ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' [nothing] -> ''Letter'' ''Letter''
Obviously, words of any length can be constructed.
Further examples in [[Regular grammar]] show how numbers can be defined via a regular grammar, and also show how a hyphenated word could be defined.
One of the most obvious limitations of a regular grammar is that it can't cope with matching brackets, so that it is impossible to write a regular grammar to describe a simple expression such as '''2 * (3+4)'''
===Level 2===
===Level 2===