Cactus Language • Syntax 9

Grammar 4

If one imposes the distinction between empty and significant types on each non‑terminal symbol in Grammar 2 then the symbols ``S" and ``T" give rise to the expanded set of non‑terminal symbols ``S", ``S'", ``T", ``T'", leaving the last three to form a new intermediate alphabet.

Grammar 4 has the intermediate alphabet \mathfrak{Q} = \{ ``S'", ``T", ``T'" \} with the set \mathfrak{K} of covering rules listed in the next display.

Cactus Language Grammar 4

Grammar 4 partitions the intermediate type T as T = \underline\varepsilon + T' in parallel fashion with the division of its overlying type as S = \underline\varepsilon + S'.  That is an option we will close off for now but leave open to consider at a later point.  It suffices to give a brief discussion of the considerations involved in choosing between grammars at this point, and then move on to the next alternative.

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 8

Grammar 3 (concl.)

Returning to the cactus language \mathfrak{C} (\mathfrak{P}) and fixing the parameter \mathfrak{P} for the moment, we have a language \mathrm{Parce} of painted and rooted cactus expressions.  It serves the purpose of efficient accounting to divide the language into two sublanguages.

  • The emptily painted and rooted cactus expressions make up the language \mathrm{EParce} which consists of a single empty string as its only sentence.

\mathrm{EParce} = \underline\varepsilon = \{ \varepsilon \}

  • The significantly painted and rooted cactus expressions make up the language \mathrm{SParce} which consists of everything else, namely, all the non‑empty strings in the language \mathrm{Parce}.

\mathrm{SParce} = \mathrm{Parce} \setminus \varepsilon

Marking the distinction between empty and significant sentences effectively categorizes each of the three classes of strings as an entity unto itself and conceives the whole of its membership as falling under a distinctive symbol, thereby obtaining the following equation among the three sublanguages.

\mathrm{SParce} = \mathrm{Parce} - \mathrm{EParce}

That makes \mathrm{Parce} the disjoint union of \mathrm{EParce} and \mathrm{SParce}.

\mathrm{Parce} = \mathrm{EParce} \cup \mathrm{SParce}

For brevity in the present case, and to serve as a generic device in similar situations, let S be the type of an arbitrary sentence, possibly empty, and let S' be the type of a non‑empty sentence.

In addition, let \underline\varepsilon be the type of the empty sentence, in effect, the language \underline\varepsilon = \{ \varepsilon \} containing a single empty string, and let a plus sign ``+" signify a disjoint union of types.  In the most general type of situation, where the type S is permitted to include the empty string, one notes the following relation among types.

S = \underline\varepsilon + S'

With the distinction between empty and significant expressions in mind, we return to the analysis of the cactus language \mathfrak{L} = \mathfrak{C} (\mathfrak{P}) = \mathrm{Parce} (\mathfrak{P}) afforded by Grammar 2, and, taking that as a point of departure, explore other avenues of possible improvement in the comprehension of its expressions.

To observe the effects of the alteration as clearly as possible in isolation from other factors it is useful to strip away the higher levels of intermediate organization presented by Grammar 3 and start again with a single intermediate symbol, as used in Grammar 2.  One way to execute that strategy leads to a style of grammar we take up next.

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 7

Grammar 3 (cont.)

Cactus Language Grammar 3

In Grammar 3, the first three Rules say a sentence (a string of type S), is either a rune (a string of type R), a foil (a string of type F), or formed by concatenating strings of those two types.

Rules 4 through 7 say a rune R is either an empty string \varepsilon, a blank symbol m_1, a paint p_j, or formed by concatenating strings of those three types.

Rule 8 characterizes a foil F as a string of the form ``(" \cdot T \cdot ``)", where T is a tract.

The last two Rules say a tract T is either a sentence S or the concatenation of a tract, a comma, and a sentence, in that order.

At this point in the succession of grammars for \mathfrak{C} (\mathfrak{P}), the problematic applications of indefinite iterations, like the kleene star operator, are now reduced to finite forms of concatenation but the problems stemming from permitting non‑terminal symbols to cover both themselves and empty strings have yet to be resolved.

A moment’s reflection on the issue raises the general question:  What is a practical strategy for accounting for the empty string in the organization of any formal language which counts it among its sentences?

One answer presenting itself is the following:  If the empty string belongs to a formal language, it suffices to count it once at the beginning of the formal account which enumerates its sentences and then move on to more interesting materials.

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 6

Grammar 3

It is possible to organize the materials of our developing grammar in a more easily graspable fashion by recognizing two recurring types of strings appearing in typical cactus expressions.  In doing so one arrives at the next two definitions.

A rune is a string of blanks and paints concatenated together.  Thus, a typical rune R is a string over \{ m_1 \} \cup \mathfrak{P}, possibly the empty string.

R \in ( \{ m_1 \} \cup \mathfrak{P} )^*

When there is no risk of confusion, the letter ``R" may be used either as a string variable ranging over the set of runes or as a type name for the class of runes.  The latter reading amounts to the recruitment of a new intermediate symbol ``R" \in \mathfrak{Q} to form a new grammar for \mathfrak{C} (\mathfrak{P}).  Thus ``R" accords grammatical recognition to any rune forming a part of a sentence in \mathfrak{C} (\mathfrak{P}).  In situations where the variant usages are likely to be confused the types of strings may be indicated by way of expressions like r <: R and W <: R.

A foil is a string of the form ``(" \cdot T \cdot ``)", where T is a tract, giving a foil F the following form.

\begin{array}{*{15}{l}}  F & = & ``(" & \cdot & S_1 & \cdot & ``," & \cdot & \ldots & \cdot & ``," & \cdot & S_k & \cdot & ``)"  \end{array}

Thus a foil is nothing other than the surcatenation of a sequence of sentences S_1, \ldots, S_k.  In the case where the sequence of sentences is empty and thus where the tract T is the empty string, we have the minimal foil F_0 = ``()".

Explicitly marking each foil F embodied in a cactus expression is tantamount to recognizing a new intermediate symbol, ``F" \in \mathfrak{Q}, further articulating the structure of expressions and expanding the grammar for the language \mathfrak{C} (\mathfrak{P}).  All the same remarks about the versatile uses of intermediate symbols, as string variables and as type names, apply again to the letter ``F".

Cactus Language Grammar 3

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 5

Grammar 2

One way to analyze the surcatenation of any number of sentences is to introduce an auxiliary type of string, not itself a sentence but a proper component of any sentence formed by surcatenation.  Doing that brings one to the following definition.

A tract is a concatenation of a finite sequence of sentences, with a literal comma ``," interpolated between each pair of adjacent sentences.  Thus, a typical tract T takes the following form.

\begin{array}{lllllllllll}  T & = & S_1 & \cdot & ``," & \cdot & \ldots & \cdot & ``," & \cdot & S_k  \end{array}

A tract of that type must be distinguished from the abstract sequence of sentences, S_1, \ldots, S_k, where the commas coming to mind, as if being called up to separate the successive sentences of the sequence, remain as partially abstract conceptions, or as signs retaining a disengaged status on the borderline between text and mind.  The kinds of commas appearing in the abstract sequence continue to exist as conceptual abstractions and fail to be cognized in a wholly explicit fashion, either as concrete tokens in the object language or as marks in the text engaging one’s parsing attention.

Returning to the painted cactus language \mathfrak{L} = \mathfrak{C} (\mathfrak{P}), it is possible to put the assembled pieces of grammar together in the light of the adopted canons of style to refine our analysis of the fact that the concept of a sentence covers any concatenation of sentences and any surcatenation of sentences, and so arrive at the following form of grammar.

Cactus Language Grammar 2

In that rendition, a string of type T is not in general a sentence itself but a proper part of speech, that is, a strictly lesser component of a sentence in any suitable ordering of sentences and their components.  In order to see how the grammatical category T gets off the ground, that is, to detect its minimal strings and to discover how its ensuing generations take their start from those, it is useful to observe that the covering rule T :> S means that T inherits all the initial conditions of S, namely, T :> \varepsilon, m_1, p_j.  In accord with those simple beginnings it comes to pass that the rule T :> T \cdot ``," \cdot S, with the substitutions T = \varepsilon and S = \varepsilon, bears the germinal implication that T :> ``,".

Grammar 2 achieves a portion of its success through a higher degree of intermediate organization.  The level of organization is reflected in the size of the intermediate alphabet \mathfrak{Q} = \{ ``T" \} but the number of symbols alone does not give a full account, as intermediate symbols are taken to serve a purpose, a purpose which is easy to recognize but not so easy to pin down and specify exactly.  Nevertheless, it is worth the trouble to explore the intermediate level of organization and its development a little further.

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 4

Grammar 1 (concl.)

Cactus Language Grammar 1

Returning to the case of the cactus language, the process of recognizing iterative or recursive types can be illustrated in the following way.  The operative phrases in the simplest form of recursive definition are its initial part and its generic part.  For the cactus language \mathfrak{C} (\mathfrak{P}), one has the following definitions of concatenation as iterated precatenation and surcatenation as iterated subcatenation, respectively.

Cactus Language Grammar 1 Display 1

Transforming the recursive definitions into grammar rules is accomplished by introducing a new pair of intermediate symbols, \mathrm{Conc} and \mathrm{Surc}, corresponding to the operations of the same names but ignoring the inflexions of their individual parameters j and k.  Recognizing the type of a sentence by means of the initial symbol S and interpreting \mathrm{Conc} and \mathrm{Surc} as names for the types of strings generated by concatenation and by surcatenation, respectively, one arrives at the following transformation of the ruling operator definitions into the form of covering grammar rules.

Cactus Language Grammar 1 Display 2

The draft of a grammar reached at this point represents a measure of improvement.  Still, it exhibits a couple of features which are desirable to amend.

  • Given the covering S :> \mathrm{Conc}, the covering rule \mathrm{Conc} :> \mathrm{Conc} \cdot S says no more than the covering rule \mathrm{Conc} :> S \cdot S.  Consequently, all the information contained in those two covering rules is already covered by the statement that S :> S \cdot S.
  • Grammar rules invoking notions of discatenation, deletion, erasure, and other forms of retrograde production may be felt to lack due elegance.  If for the sake of the aesthetic in question one entertains for a moment keeping open the option of adopting that style of critique, it becomes necessary to backtrack a little bit, to experiment with withdrawing all forms of elliptical operators, but without, of course, eliding the record of having considered them.

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 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