Cactus Language • Syntax 3

Grammar 1 (cont.)

The degree of intermediate organization in a grammar is measured by the number of its intermediate symbols and the complexity of their mutual interplay within the frame of the grammar’s productions.

Grammar 1 has no intermediate symbols at all, \mathfrak{Q} = \varnothing, and so remains at a trivial degree of intermediate organization.  Some additions to the list of intermediate symbols are practically obligatory in order to arrive at any reasonable grammar at all.  Other inclusions have a more optional character, though useful from the standpoints of clarity and ease of comprehension.

One of the troubles perceived to affect Grammar 1 is the way it wastes so much of the available potential for efficient description in recounting over and over again the simple fact that the empty string is present in the language.  The problem arises partly from the covering relation S :> S^*, which has the following implications.

\begin{array}{lcccccccccccc}  S & :> & S^* & = & \underline\varepsilon & \cup & S & \cup & S \cdot S & \cup & S \cdot S \cdot S & \cup & \ldots \end{array}

There is nothing wrong with the more expansive pan of the covered equation, since it follows straightforwardly from the definition of the kleene star operation.  But the statement S :> S^* is not a very productive piece of information, in the sense of telling us much about the language falling under the type of a sentence S.

In particular, S :> S^* implies S :> \underline\varepsilon.  Since \underline\varepsilon \cdot \mathfrak{L} = \mathfrak{L} \cdot \underline\varepsilon = \mathfrak{L} for any formal language \mathfrak{L}, the empty string \varepsilon is counted over and over in every term of the union, and every non‑empty sentence under S appears again and again in every term of the union following the initial appearance of S.  As a result, the overall style of characterization has to be classified as true but not very informative.

If at all possible, one prefers to partition the language of interest into a disjoint union of subsets, thereby accounting for each sentence under its proper term, and one whose place under the sum serves as a useful parameter of its character or its complexity.  Such an ideal form of description is not always possible to achieve but it is usually worth the trouble to actualize it whenever one can.

Suppose one tries to deal with the problem by eliminating each use of the kleene star operation, by reducing it to a purely finitary set of steps, or by finding another way to cover the sublanguage it is used to generate.  That amounts, in effect, to recognizing a type, a complex process involving the following steps.

  • Noticing a category of strings which is generated by iteration or recursion.
  • Acknowledging the fact that it needs to be covered by a non‑terminal symbol.
  • Making a note of it by instituting an explicitly‑named grammatical category.

In sum, one introduces a non‑terminal symbol for each type of sentence and each part of speech or sentential component generated by means of iteration or recursion under the ruling constraints of the grammar.  To do that one needs to analyze the iteration of each grammatical operation in a way which is analogous to a mathematically inductive definition but further in a way which is not forced explicitly to recognize a distinct and separate type of expression merely to account for and recount every increment in the parameter of iteration.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Syntax 2

Grammar 1 (cont.)

In the process of developing a grammar for a language we encounter a number of organizational, pragmatic, and stylistic options whose moment to moment choices decide the ongoing direction of the work in progress and the impacts of whose evaluation work in tandem to determine the shape of the grammar turned out in the end.  Most salient among the critical issues are three described in the following way.

  • The degree of intermediate organization in a grammar.
  • The distinction between empty and significant strings, and thus the distinction between empty and significant types of strings.
  • The principle of intermediate significance, a constraint on the grammar which arises from considering the interaction of the first two issues.

In responding to the collective issues, it is advisable at first to proceed in a stepwise fashion, all the better to accommodate the chances of pursuing a series of parallel developments in the grammar, to allow for the possibility of reversing many steps in its development, indeed, to take into account the almost certain inevitability of having to revisit, revise, and reverse many prior decisions about how to proceed toward an optimal description or a satisfactory grammar for the language.  Doing all that means exploring the effects of various alterations and innovations as independently from each other as possible.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Syntax 1

Grammar 1

Grammar 1 is something of a misnomer.  It is nowhere near exemplifying any kind of a standard form and it’s put forth only as a starting point for the initiation of more respectable grammars.  Such as it is, it uses the terminal alphabet \mathfrak{A} = \mathfrak{M} \cup \mathfrak{P} coming with the territory of the cactus language \mathfrak{C} (\mathfrak{P}), it specifies \mathfrak{Q} = \varnothing, in other words, it employs no intermediate symbols, and it embodies the covering set \mathfrak{K} as listed in the following display.

Cactus Language Grammar 1

The last two rules of Grammar 1 dictate the following typings.

  1. The concept of a sentence in \mathfrak{L} covers any concatenation of sentences in \mathfrak{L}, that is, any finite number of freely chosen sentences available to be concatenated one after another.
  2. The concept of a sentence in \mathfrak{L} covers any surcatenation of sentences in \mathfrak{L}, that is, any string opening with a ``\mathrm{(}", continuing with a sentence, possibly empty, following with a finite number of phrases of the form ``\mathrm{,}" \cdot S, and closing with a ``\mathrm{)}".

The above appears to be just about the most concise description of the cactus language \mathfrak{C} (\mathfrak{P}) one can imagine but there are a couple of problems commonly felt to afflict its style of presentation and to make it less than completely acceptable.  Briefly stated, the problems turn on the following properties of the formulation.

  • The invocation of the kleene star operation is not reduced to a manifestly finitary form.
  • The type S indicative of a sentence is allowed to cover not only itself but also the empty string.

We’ll discuss those issues at first in general, and especially in regard to how the two features interact with one another, and then we’ll return to address in further detail the questions they engender on their individual bases.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Preliminaries 17

A certain degree of flexibility in the use of covering relations is typically allowed in practice.  Where there is little danger of confusion we may allow symbols to stand equivocally either for individual strings or for their types.

There is a measure of consistency to this practice, considering the fact that perfectly individual entities are rarely if ever grasped by means of signs and finite expressions, since every appearance of an apparent token is only a type of more particular tokens, ultimately leaving no recourse but to the order of discerning interpretation which has to decide exactly how every sign is intended.

Thus we have sufficient license for expressions of the form t <: T and T <: S, where the symbols t, T, S may be taken to signify either the tokens or the subtypes of their covering types.

Note.  For some time to come in the discussion that follows, although we will continue to focus on the cactus language as our principal object example, our more general purpose will be to develop the subject matter of formal languages and grammars in general.  We will do this by taking up a particular method of stepwise refinement which leads us to extract a rigorous formal grammar for the cactus language, starting with little more than a rough description of the target language and applying a systematic analysis to develop a sequence of increasingly more effective and exact approximations to the desired grammar.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Preliminaries 16

The following definitions round out the concepts we need to begin applying formal grammar theory to the efficient description of formal languages, in particular, the family of cactus languages.

It is convenient to refer to the full set of symbols in \{ ``S" \} \cup \mathfrak{Q} \cup \mathfrak{A} as the augmented alphabet of the candidate formal grammar for \mathfrak{L} and thus to refer to the strings in ( \{ ``S" \} \cup \mathfrak{Q} \cup \mathfrak{A} )^* as the augmented strings of the grammar for \mathfrak{L}, in effect, articulating the forms superimposed on a language by one of its conceivable grammars.

In certain settings it becomes desirable to separate the augmented strings containing the symbol ``S" from all other cases of augmented strings.  In those situations the strings in the disjoint union \{ ``S" \} \cup (\mathfrak{Q} \cup \mathfrak{A} )^* are known as the sentential forms of the associated grammar.

In forming a grammar for a language, statements of the form W :> W', where W and W' are augmented strings or sentential forms of specified types which depend on the style of the grammar being sought, are variously known as characterizations, covering rules, productions, rewrite rules, subsumptions, transformations, or typing rules.  Statements of that form are collected together in a set \mathfrak{K} which serves to complete the definition of the formal grammar in question.

The relation S :> T has the converse form T <: S which may be read as T is covered by S and understood in the sense that T is of the type S.  Depending on the context, T <: S can be taken in one of the following two ways.

  • Treating T as a string variable, it means the individual string T is an instance of the type S.
  • Treating T as a type name, it means every string of the type T is an instance of the type S.

In light of the above conventions, an expression of the form t <: T can be read in all the ways one typically reads an expression of the form t : T.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Preliminaries 15

A notation of the form S :> T was introduced last time to indicate a category of grammatical relationships whose sense is suggested by any of the following readings.

\begin{array}{l}  S ~\mathrm{covers}~ T  \\[2pt]  S ~\mathrm{governs}~ T  \\[2pt]  S ~\mathrm{rules}~ T  \\[2pt]  S ~\mathrm{subsumes}~ T  \\[2pt]  S ~\mathrm{types~over}~ T  \end{array}

For the moment it’s enough to call S :> T a covering relation, reading it as S ~\mathrm{covers}~ T.

In what follows the letter ``S" indicates the type of a sentence in the contemplated language \mathfrak{L}.  The letter ``S" is the initial symbol or sentence symbol of the candidate formal grammar for \mathfrak{L}.

Generally speaking, any number of letters like ``T", signifying other types of strings, will be found necessary for a reasonable account or rational reconstruction of the sentences in \mathfrak{L}.  The additional letters are known as intermediate symbols and collected together in the set \mathfrak{Q}.

Combining the singleton set \{ ``S" \} whose sole member is the initial symbol with the set \mathfrak{Q} of intermediate symbols results in the set \{ ``S" \} \cup \mathfrak{Q} of non‑terminal symbols.  Even though \mathfrak{Q} is strictly only the set of intermediate symbols, it is handy to use q as a typical variable ranging over the full set of non‑terminal symbols, q \in \{ ``S" \} \cup \mathfrak{Q}.

To complete the package, the alphabet \mathfrak{A} of the language \mathfrak{L} may also be referred to as the set of terminal symbols.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Preliminaries 14

A notation of the form S :> T is introduced to indicate a category of grammatical relationships whose sense is suggested by any of the following readings.

\begin{array}{l}  S ~\mathrm{covers}~ T  \\[2pt]  S ~\mathrm{governs}~ T  \\[2pt]  S ~\mathrm{rules}~ T  \\[2pt]  S ~\mathrm{subsumes}~ T  \\[2pt]  S ~\mathrm{types~over}~ T  \end{array}

The form S :> T plays a number of roles in the description of formal languages by means of formal grammars, flexible enough to be read in the following variety of senses.

Individual
The named or quoted string T is being typed as a sentence S of the language \mathfrak{L}.
Extensional
Each member of the set T also belongs to the set S of sentences in the language \mathfrak{L}.
Intensional
The quality of being T entails the quality S of being a sentence in the language \mathfrak{L}.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Preliminaries 13

Consider what effects that might conceivably
have practical bearings you conceive the
objects of your conception to have.  Then,
your conception of those effects is the
whole of your conception of the object.

Charles S. Peirce • Issues of Pragmaticism

We have before us what appears to be a maximally concise description of our subject matter.

The painted cactus language with paints in the set \mathfrak{P} = \{ p_j : j \in J \} is the formal language \mathfrak{L} = \mathfrak{C} (\mathfrak{P}) \subseteq \mathfrak{A}^* = (\mathfrak{M} \cup \mathfrak{P})^* defined as follows.

\begin{array}{ll}  \text{PC 1.} & \text{The blank symbol}~ m_1 ~\text{is a sentence.}  \\  \text{PC 2.} & \text{The paint}~ p_j ~\text{is a sentence for each}~ j ~\text{in}~ J.  \\  \text{PC 3.} & \mathrm{Conc}^0 ~\text{and}~ \mathrm{Surc}^0 ~\text{are sentences.}  \\  \text{PC 4.} & \text{For each positive integer}~ n,  \\  & \text{if}~ s_1, \ldots, s_n ~\text{are sentences}  \\  & \text{then}~ \mathrm{Conc}_{k=1}^n s_k ~\text{is a sentence}  \\  & \text{and}~ \mathrm{Surc}_{k=1}^n s_k ~\text{is a sentence.}  \end{array}

Here we encounter a problem.  The very conciseness of that description presents an obstacle to understanding, glossing over infinities and divinities of detail which must be comprehended in effectively finite form, especially if we have in mind developing a fully computational parser.

A start in that direction, taking steps toward an effective description of cactus languages, a finitary conception of their membership conditions, and a bounded characterization of a typical sentence of that form, can be made by recasting the above description of cactus expressions into the pattern of what is called, more or less roughly, a formal grammar.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Preliminaries 12

We are engaged in teasing out the consequences of the following description of our subject.

The painted cactus language with paints in the set \mathfrak{P} = \{ p_j : j \in J \} is the formal language \mathfrak{L} = \mathfrak{C} (\mathfrak{P}) \subseteq \mathfrak{A}^* = (\mathfrak{M} \cup \mathfrak{P})^* defined as follows.

\begin{array}{ll}  \text{PC 1.} & \text{The blank symbol}~ m_1 ~\text{is a sentence.}  \\  \text{PC 2.} & \text{The paint}~ p_j ~\text{is a sentence for each}~ j ~\text{in}~ J.  \\  \text{PC 3.} & \mathrm{Conc}^0 ~\text{and}~ \mathrm{Surc}^0 ~\text{are sentences.}  \\  \text{PC 4.} & \text{For each positive integer}~ n,  \\  & \text{if}~ s_1, \ldots, s_n ~\text{are sentences}  \\  & \text{then}~ \mathrm{Conc}_{k=1}^n s_k ~\text{is a sentence}  \\  & \text{and}~ \mathrm{Surc}_{k=1}^n s_k ~\text{is a sentence.}  \end{array}

Only one thing remains to cast that description of cactus language into a commonly acceptable form.  As presently formulated, the principle PC 4 appears to be attempting to define an infinite number of new concepts all in a single step, at least, it appears to invoke the indefinitely long sequences of operators \mathrm{Conc}^n and \mathrm{Surc}^n for all n > 0.

As a general rule one prefers to work with effectively finite descriptions of conceptual objects.  That means restricting each description to a finite number of schematic principles, each of which involves a finite number of schematic effects.  In that way we hope to arrive at a finite number of schemata explicitly relating conditions to results.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments

Cactus Language • Preliminaries 11

Given the idea of a Parce on \mathfrak{P} as a member of the cactus language \mathfrak{C}(\mathfrak{P}) a number of frequently occurring sublanguages and commonly invoked operations on their expressions can now be given succinct definition.

A bare Parce, a bit loosely referred to as a bare cactus expression, is a Parce on the empty palette \mathfrak{P} = \varnothing.  A bare Parce is a sentence in the bare cactus language, variously notated as follows.

\mathfrak{C}^0 = \mathfrak{C} (\varnothing) = \mathrm{Parce}^0 = \mathrm{Parce}(\varnothing)

That set of strings, regarded as a formal language in its own right, is a sublanguage of every cactus language \mathfrak{C}(\mathfrak{P}).  A bare cactus expression is commonly encountered in practice when one has occasion to start with an arbitrary Parce and then finds reason to delete or erase all its paints.

Resources

cc: Academia.edu • BlueSky • Laws of FormMathstodonResearch Gate
cc: Conceptual GraphsCyberneticsStructural ModelingSystems Science

Posted in Automata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Differential Logic, Equational Inference, Formal Grammars, Formal Languages, Graph Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Propositional Calculus, Visualization | Tagged , , , , , , , , , , , , , , , , | 2 Comments