12,089
edits
Changes
Directory:Jon Awbrey/Papers/Inquiry Driven Systems : Part 6 (view source)
Revision as of 14:04, 26 April 2012
, 14:04, 26 April 2012→6.7. Basic Notions of Formal Language Theory: rephrase
This section collects the material on formal language theory that is needed for the rest of this work.
This section collects the material on formal language theory that is needed for the rest of this work.
A '''formal language''' is a countable set of '''expressions''', each of which is a finite sequence of elements taken from a finite set of '''symbols'''. The primitive symbols that are used to generate the expressions of a formal language are collectively called its '''alphabet''' or its '''lexicon''', depending on whether the expressions of the language are intuitively regarded as '''words''' or as '''sentences''', respectively.
A '''formal language''' is a countable set of '''expressions''', each of which is a finite sequence of elements taken from a finite set of '''symbols'''. The primitive symbols that are used to generate the expressions of a formal language are collectively called its '''alphabet''' or its '''lexicon''', depending on whether the expressions of the language are regarded on analogy with '''words''' or '''sentences''', respectively.
So long as one considers only words or only sentences, that is, only one level of finite sequences of symbols, it does not matter essentially what the sequences are called. Unless otherwise specified, a formal language is taken by default to be a ''one-level formal language'', containing only a single level of sequences. If one wants to consider both words and sentences, that is, finite sequences of symbols and then finite sequences of these lower level sequences, all in the same context of discussion, then one has to move up to an essentially more powerful concept, that of a ''two-level formal language''.
So long as one considers only words or only sentences, that is, only one level of finite sequences of symbols, it does not matter essentially what the sequences are called. Unless otherwise specified, a formal language is taken by default to be a ''one-level formal language'', containing only a single level of sequences. If one wants to consider both words and sentences, that is, finite sequences of symbols and then finite sequences of these lower level sequences, all in the same context of discussion, then one has to move up to an essentially more powerful concept, that of a ''two-level formal language''.