SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 155:
Line 155: − + + + Line 173:
Line 175: − +
→Chomsky hierarchy: define symbol for [nothing], more limitations
+ The '''recogniser''' column indicates the type of mathematical or computer science theoretical model needed to recognise that a sentence belongs to a language, essentially by applying the transformation rules in reverse to work backwards from the actual words in order to finish up with a ''sentence'' (in programming languages the starting concept is usually a ''program''). A finite automaton uses only a small fixed amount of memory, operates in time proportional to the length of the input, and always reaches a decision, while a Turing machine may use an infinite amount of memory and time and may fail to reach a decision (may never stop).
+ The '''recogniser''' column indicates the type of mathematical or computer science theoretical model needed to recognise that a sentence belongs to a language, essentially by applying the transformation rules in reverse to work backwards from the actual words in order to finish up with a ''sentence'' (in programming languages the starting concept is usually a ''program''). A finite automaton uses only a small fixed amount of memory, operates in time proportional to the length of the input, and always reaches a decision, while a Turing machine may use an infinite amount of memory and time and may fail to reach a decision (may never stop).
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.
In the linguistic literature, [nothing] is often represented by the symbol '''ε'''.
The descriptions of the various Chomsky levels which follows are presented in reverse order, so as to work up from a simple case to a rather complicated case.
===Level 3: regular grammar===
===Level 3: regular grammar===
:''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.
Obviously, words of any length can be constructed. Trying to further constrain the productions to produce words which are more English-like is much more difficult - how do you insist on at least one vowel or on no more than 5 consecutive consonants (e.g. as in 'strenghts').
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.
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.