SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 142:
Line 142: − + Line 150:
Line 150: − + − ===Level 0===+ + + − + − + + +
→Chomsky hierarchy: indicate what a '''recogniser''' is.
{| class="wikitable"
{| class="wikitable"
!| Chomsky<br>number || linguistic name || Rule constraints || Recogniser || Notes
!| Chomsky<br>number || linguistic name || Rule constraints || Recogniser+ || Notes
|-
|-
| 0 || recursively enumerable || [anything] -> [anything] || Turing machine || most human languages
| 0 || recursively enumerable || [anything] -> [anything] || Turing machine || most human languages
| 2 || context-free || ''A'' -> [anything] || non-deterministic push-down automaton || syntax analysis for most programming languages
| 2 || context-free || ''A'' -> [anything] || non-deterministic push-down automaton || syntax analysis for most programming languages
|-
|-
| 3 || regular || ''A'' -> [nothing]<br>''A'' -> '''xyz'''<br>''A'' -> '''xyz''' ''B'' || finite automaton || lexical analysis (combining characters into words/tokens)
| 3 || regular || ''A'' -> [nothing]<br>''A'' -> '''xyz'''<br>''A'' -> '''xyz''' ''B'' || finite automaton<br>or finite state machine || lexical analysis (combining characters into words/tokens)
|}
|}
+ 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.
===Level 1===
===Level 3===
===Level 2===
===Level 2===
===Level 3===
===Level 1===
===Level 0===
==References==
==References==