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

Cactus Language • Preliminaries 10

Last time we arrived at the following definition 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}

A sentence of \mathfrak{C} (\mathfrak{P}) is known as a painted and rooted cactus expression on the palette \mathfrak{P}, more briefly as a Parce on \mathfrak{P}, or simply as a cactus expression when the context is clear.

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 • Discussion 2

Re: Cactus Language • Preliminaries 9
Re: Cactus Language • Discussion 1
Re: Alex Shkotin

AS:
Interesting language.  It’s unusual to treat “ ” as a sentence.  Usually it is just a separator for other lexemes.

Are the following correct?

  • One blank in brackets i.e. ``\texttt{(~)}" is a sentence.
  • Two blanks in brackets i.e. ``\texttt{(~~)}" is not a sentence.

Are the three strings below sentences?

  • \texttt{(,,)}
  • \texttt{(~,~,~)}
  • \texttt{((),(),())}

And at last.  You use your own notation to define formal language.  Is it correct that this language is context‑free?

Thanks for the questions, Alex,

As I mentioned in the first discussion post, the current presentation of Cactus Language is rather abstract and formal because that’s what we need to implement a fully computational parser for the family of languages we have in mind.  That is all well and good but it does leave us hanging when it comes to motivation and remembering why we are bothering with such a mass of formal detail.

When I find myself getting lost in syntactic abstractions it’s a good idea to stop and remind myself what led me to explore the computational powers of cactus graphs in the first place.  In my case it began with C.S. Peirce’s and Spencer Brown’s systems of logical graphs.  Two developments of that work which take up the story much nearer to scratch can be found on the following pages.

Short answers to the above questions —

  • One blank in brackets i.e. ``\texttt{(~)}" is a sentence.
  • Two blanks in brackets i.e. ``\texttt{(~~)}" is a sentence.
    (Blanks can be concatenated any number of times.)
  • All three of the other strings listed above are sentences.

Finally, I think cactus languages are context‑free as I think the last best grammars I constructed for them are context‑free, but that is one of those hazy memories I’ll need to check out on the current pass through the material.

Resources

cc: Academia.edu • BlueSky • Laws of Form • Mathstodon • Research 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