Context-Free A<anything> Push-Down Automaton Context-Sensitive c1Ac2c1<anything>c2 Linear Bounded Automaton Recursively Enumerable No Restrictions on Rules Turing Machine (= 2 Stack PDA) The point I want to make fortunately does not require us to delve very deeply into the information summarized in this table. A few basic points will suffice. The first thing to realize is that not all vocabularies in the syntactic sense we have been pursuing can be read and written by finite-state automata. For instance, it can be shown that no finite-state automaton is to deploy the vocabulary anbn, defined over the alphabet {a,b}, which consists of all strings of any arbitrary number of followed by the same number of The idea behind the ‘a’s ‘b’s. proof is that in order to tell whether the right number of follow the (when reading) or to ‘b’s ‘a’s produce the right number of (when writing), the automaton must somehow keep track of ‘b’s how many have been processed (read or written). The only way an FSA can store ‘a’s information is by being in one state rather than another. So, it could be in one state—or in one of a class of states—if one has been processed, another if two have, and so on. But by ‘a’ definition, a finite-state automaton only has a finite number of states, and that number is fixed in of receiving its input or producing its output. Whatever that number of states is, and advance whatever system it uses to code numbers into states (it need not be one-to-one—it could use a decimal coding, for instance), there will be some number of that is so large that the ‘a’s automaton runs out of states before it finishes counting. But the vocabulary in question consists of arbitrarily long strings of and In fact, it is possible to say exactly which vocabularies ‘a’s ‘b’s. finite-state automata (specifiable by digraphs and state-tables of the sort illustrated above) are capable of deploying. These are called the vocabularies (or languages). ‘regular’
Context-Free A<anything> Push-Down Automaton Context-Sensitive c1Ac2c1<anything>c2 Linear Bounded Automaton Recursively Enumerable No Restrictions on Rules Turing Machine (= 2 Stack PDA) The point I want to make fortunately does not require us to delve very deeply into the information summarized in this table. A few basic points will suffice. The first thing to realize is that not all vocabularies in the syntactic sense we have been pursuing can be read and written by finite-state automata. For instance, it can be shown that no finite-state automaton is to deploy the vocabulary anbn, defined over the alphabet {a,b}, which consists of all strings of any arbitrary number of ‘a’s followed by the same number of ‘b’s. The idea behind the proof is that in order to tell whether the right number of ‘b’s follow the ‘a’s (when reading) or to produce the right number of ‘b’s (when writing), the automaton must somehow keep track of how many ‘a’s have been processed (read or written). The only way an FSA can store information is by being in one state rather than another. So, it could be in one state—or in one of a class of states—if one ‘a’ has been processed, another if two have, and so on. But by definition, a finite-state automaton only has a finite number of states, and that number is fixed in advance of receiving its input or producing its output. Whatever that number of states is, and whatever system it uses to code numbers into states (it need not be one-to-one—it could use a decimal coding, for instance), there will be some number of ‘a’s that is so large that the automaton runs out of states before it finishes counting. But the vocabulary in question consists of arbitrarily long strings of ‘a’s and ‘b’s. In fact, it is possible to say exactly which vocabularies finite-state automata (specifiable by digraphs and state-tables of the sort illustrated above) are capable of deploying. These are called the ‘regular’ vocabularies (or languages).
Analytic%20Pragmatism%20Expressivism%20and%20Modality%2014-10-2%20a.docx