Generalities About Formal Grammars
12 views
Skip to first unread message
Jon Awbrey
Jun 29, 2025, 10:36:38 AMJun 29
to Conceptual Graphs, Cybernetic Communications, Structural Modeling, SysSciWG
Generalities About Formal Grammars • 1
• https://inquiryintoinquiry.com/2025/06/28/generalities-about-formal-grammars-1/
It is fitting to wrap up the foregoing developments by summarizing the notion
of a formal grammar which appeared to evolve in the analysis of cactus languages.
For the sake of future reference and further application it is useful to extract
a scheme of formalization potentially holding for arbitrary formal languages.
The following presentation is adapted with minor modifications from the treatment
in Denning, Dennis, and Qualitz (1978), “Machines, Languages, and Computation”,
Prentice‑Hall, Englewood Cliffs, NJ, (pp. 60–61).
A “formal grammar” ‡G‡ is defined by a four‑tuple ‡G‡ = (“S”, ‡Q‡, ‡A‡, ‡K‡)
of the following form.
• “S” is the “initial”, “special”, “start”, or “sentence symbol”. The letter “S”
plays that role solely in a special setting, so its employment as such creates
no confusion with its possible use as a string variable or a sentence variable.
• ‡Q‡ = {q₁, …, qₘ} is a finite set of “intermediate symbols”, all distinct from “S”.
• ‡A‡ = {a₁, …, aₙ} is a finite set of “terminal symbols”, also known as the
“alphabet” of ‡G‡, all distinct from “S” and disjoint from ‡Q‡. Depending
on the particular conception of the language ‡L‡ covered, generated, governed,
or ruled by the grammar ‡G‡, that is, whether ‡L‡ is conceived to be a set of
words, sentences, paragraphs, or more extended structures of discourse, it
is usual to describe ‡A‡ as the alphabet, lexicon, vocabulary, liturgy, or
phrase book of both the grammar ‡G‡ and the language ‡L‡ it regulates.
• ‡K‡ is a finite set of “characterizations”. Depending on how they
come into play, the elements of ‡K‡ may be described as covering rules,
formations, productions, rewrite rules, subsumptions, transformations,
or typing rules.
Resources —
Generalities About Formal Grammars
• https://oeis.org/wiki/Cactus_Language_%E2%80%A2_Part_2
Survey of Animated Logical Graphs
• https://inquiryintoinquiry.com/2025/05/02/survey-of-animated-logical-graphs-8/
Survey of Theme One Program
• https://inquiryintoinquiry.com/2025/05/06/survey-of-theme-one-program-7/
Regards,
Jon
cc: https://www.academia.edu/community/5wpbeN
cc: https://www.researchgate.net/post/Generalities_About_Formal_Grammars
• https://inquiryintoinquiry.com/2025/06/28/generalities-about-formal-grammars-1/
It is fitting to wrap up the foregoing developments by summarizing the notion
of a formal grammar which appeared to evolve in the analysis of cactus languages.
For the sake of future reference and further application it is useful to extract
a scheme of formalization potentially holding for arbitrary formal languages.
The following presentation is adapted with minor modifications from the treatment
in Denning, Dennis, and Qualitz (1978), “Machines, Languages, and Computation”,
Prentice‑Hall, Englewood Cliffs, NJ, (pp. 60–61).
A “formal grammar” ‡G‡ is defined by a four‑tuple ‡G‡ = (“S”, ‡Q‡, ‡A‡, ‡K‡)
of the following form.
• “S” is the “initial”, “special”, “start”, or “sentence symbol”. The letter “S”
plays that role solely in a special setting, so its employment as such creates
no confusion with its possible use as a string variable or a sentence variable.
• ‡Q‡ = {q₁, …, qₘ} is a finite set of “intermediate symbols”, all distinct from “S”.
• ‡A‡ = {a₁, …, aₙ} is a finite set of “terminal symbols”, also known as the
“alphabet” of ‡G‡, all distinct from “S” and disjoint from ‡Q‡. Depending
on the particular conception of the language ‡L‡ covered, generated, governed,
or ruled by the grammar ‡G‡, that is, whether ‡L‡ is conceived to be a set of
words, sentences, paragraphs, or more extended structures of discourse, it
is usual to describe ‡A‡ as the alphabet, lexicon, vocabulary, liturgy, or
phrase book of both the grammar ‡G‡ and the language ‡L‡ it regulates.
• ‡K‡ is a finite set of “characterizations”. Depending on how they
come into play, the elements of ‡K‡ may be described as covering rules,
formations, productions, rewrite rules, subsumptions, transformations,
or typing rules.
Resources —
Generalities About Formal Grammars
• https://oeis.org/wiki/Cactus_Language_%E2%80%A2_Part_2
Survey of Animated Logical Graphs
• https://inquiryintoinquiry.com/2025/05/02/survey-of-animated-logical-graphs-8/
Survey of Theme One Program
• https://inquiryintoinquiry.com/2025/05/06/survey-of-theme-one-program-7/
Regards,
Jon
cc: https://www.academia.edu/community/5wpbeN
cc: https://www.researchgate.net/post/Generalities_About_Formal_Grammars
Jon Awbrey
Jul 2, 2025, 2:30:27 PMJul 2
to Conceptual Graphs, Cybernetic Communications, Structural Modeling, SysSciWG
Generalities About Formal Grammars • 2
• https://inquiryintoinquiry.com/2025/07/01/generalities-about-formal-grammars-2/
Characterizations —
Recall that a formal grammar ‡G‡ is defined by a 4‑tuple ‡G‡ = (“S”, ‡Q‡, ‡A‡, ‡K‡)
where “S” is the initial, special, start, or sentence symbol, ‡Q‡ is a finite set
of intermediate symbols, ‡A‡ is a finite set of terminal symbols, also known as the
alphabet of ‡G‡, and ‡K‡ is a finite set of characterizations, variously described as
• Augmented Alphabet
The symbols in {“S”} ∪ ‡Q‡ ∪ ‡A‡ form the augmented alphabet of ‡G‡.
• Non‑Terminal Symbols
The symbols in {“S”} ∪ ‡Q‡ are the non‑terminal symbols of ‡G‡.
• Non‑Initial Symbols
The symbols in ‡Q‡ ∪ ‡A‡ are the non‑initial symbols of ‡G‡.
• Augmented Strings
The strings in ({“S”} ∪ ‡Q‡ ∪ ‡A‡)* are the augmented strings for ‡G‡.
• Sentential Forms
The strings in {“S”} ∪ (‡Q‡ ∪ ‡A‡)* are the sentential forms for ‡G‡.
Each member of ‡K‡ is an ordered pair of strings (S₁, S₂) taking the following form.
• S₁ = Q₁ ∙ q ∙ Q₂
• S₂ = Q₁ ∙ W ∙ Q₂
S₁ and S₂ are augmented strings for ‡G‡, in particular, sentential forms
with S₁ being a non‑empty string and S₂ being a possibly empty string.
The element q is a non‑terminal symbol, in other words, q ∈ {“S”} ∪ ‡Q‡.
The elements Q₁, Q₂, and W are possibly empty strings of non‑initial symbols,
that is to say, Q₁, Q₂, W ∈ (‡Q‡ ∪ ‡A‡)*.
In practice the couplets belonging to ‡K‡ are used to derive, generate,
or produce sentences of the corresponding language ‡L‡ = ‡L‡(‡G‡).
The language ‡L‡ is then said to be governed, licensed, or regulated
by the grammar ‡G‡, a circumstance expressed in the form ‡L‡ = ⟨‡G‡⟩.
Because it helps to focus our attention on the the more active dynamic
aspects of using grammars to generate languages it is usual to write
abstract characterizations like (S₁, S₂) and specific characterizations
like (Q₁∙q∙Q₂, Q₁∙W∙Q₂) in the following forms.
• S₁ :> S₂
• Q₁∙q∙Q₂ :> Q₁∙W∙Q₂
The characterization S₁ :> S₂ amounts to a grammatical license to transform
a string of the form Q₁∙q∙Q₂ into a string of the form Q₁∙W∙Q₂, in effect,
replacing the non‑terminal symbol q with the non‑initial string W in any
selected, preserved, and closely adjoining context of the form Q₁∙__∙Q₂.
In that application the notation S₁ :> S₂ can be read to say that S₁
produces S₂ or that S₁ transforms into S₂.
Resources —
Generalities About Formal Grammars
• https://oeis.org/wiki/Cactus_Language_%E2%80%A2_Part_2
Survey of Animated Logical Graphs
• https://inquiryintoinquiry.com/2025/05/02/survey-of-animated-logical-graphs-8/
Survey of Theme One Program
• https://inquiryintoinquiry.com/2025/05/06/survey-of-theme-one-program-7/
Regards,
Jon
cc: https://www.academia.edu/community/LmawZP
cc: https://www.researchgate.net/post/Generalities_About_Formal_Grammars
• https://inquiryintoinquiry.com/2025/07/01/generalities-about-formal-grammars-2/
Characterizations —
Recall that a formal grammar ‡G‡ is defined by a 4‑tuple ‡G‡ = (“S”, ‡Q‡, ‡A‡, ‡K‡)
where “S” is the initial, special, start, or sentence symbol, ‡Q‡ is a finite set
of intermediate symbols, ‡A‡ is a finite set of terminal symbols, also known as the
alphabet of ‡G‡, and ‡K‡ is a finite set of characterizations, variously described as
covering rules, formations, productions, rewrite rules, subsumptions, transformations,
or typing rules.
To describe the variety of elements in ‡K‡ it helps to define a few additional terms.
or typing rules.
• Augmented Alphabet
The symbols in {“S”} ∪ ‡Q‡ ∪ ‡A‡ form the augmented alphabet of ‡G‡.
• Non‑Terminal Symbols
The symbols in {“S”} ∪ ‡Q‡ are the non‑terminal symbols of ‡G‡.
• Non‑Initial Symbols
The symbols in ‡Q‡ ∪ ‡A‡ are the non‑initial symbols of ‡G‡.
• Augmented Strings
The strings in ({“S”} ∪ ‡Q‡ ∪ ‡A‡)* are the augmented strings for ‡G‡.
• Sentential Forms
The strings in {“S”} ∪ (‡Q‡ ∪ ‡A‡)* are the sentential forms for ‡G‡.
Each member of ‡K‡ is an ordered pair of strings (S₁, S₂) taking the following form.
• S₁ = Q₁ ∙ q ∙ Q₂
• S₂ = Q₁ ∙ W ∙ Q₂
S₁ and S₂ are augmented strings for ‡G‡, in particular, sentential forms
with S₁ being a non‑empty string and S₂ being a possibly empty string.
The element q is a non‑terminal symbol, in other words, q ∈ {“S”} ∪ ‡Q‡.
The elements Q₁, Q₂, and W are possibly empty strings of non‑initial symbols,
that is to say, Q₁, Q₂, W ∈ (‡Q‡ ∪ ‡A‡)*.
In practice the couplets belonging to ‡K‡ are used to derive, generate,
or produce sentences of the corresponding language ‡L‡ = ‡L‡(‡G‡).
The language ‡L‡ is then said to be governed, licensed, or regulated
by the grammar ‡G‡, a circumstance expressed in the form ‡L‡ = ⟨‡G‡⟩.
Because it helps to focus our attention on the the more active dynamic
aspects of using grammars to generate languages it is usual to write
abstract characterizations like (S₁, S₂) and specific characterizations
like (Q₁∙q∙Q₂, Q₁∙W∙Q₂) in the following forms.
• S₁ :> S₂
• Q₁∙q∙Q₂ :> Q₁∙W∙Q₂
The characterization S₁ :> S₂ amounts to a grammatical license to transform
a string of the form Q₁∙q∙Q₂ into a string of the form Q₁∙W∙Q₂, in effect,
replacing the non‑terminal symbol q with the non‑initial string W in any
selected, preserved, and closely adjoining context of the form Q₁∙__∙Q₂.
In that application the notation S₁ :> S₂ can be read to say that S₁
produces S₂ or that S₁ transforms into S₂.
Resources —
Generalities About Formal Grammars
• https://oeis.org/wiki/Cactus_Language_%E2%80%A2_Part_2
Survey of Animated Logical Graphs
• https://inquiryintoinquiry.com/2025/05/02/survey-of-animated-logical-graphs-8/
Survey of Theme One Program
• https://inquiryintoinquiry.com/2025/05/06/survey-of-theme-one-program-7/
Regards,
Jon
cc: https://www.researchgate.net/post/Generalities_About_Formal_Grammars
Jon Awbrey
Jul 4, 2025, 10:32:40 AMJul 4
to Conceptual Graphs, Cybernetic Communications, Structural Modeling, SysSciWG
Generalities About Formal Grammars • 3
• https://inquiryintoinquiry.com/2025/07/03/generalities-about-formal-grammars-3/
Derivations —
An “immediate derivation” in ‡G‡ is an ordered pair (W, W′) of
sentential forms in ‡G‡ such that the following conditions hold.
• W = Q₁ ∙ X ∙ Q₂
• W' = Q₁ ∙ Y ∙ Q₂
• (X, Y) ∈ ‡K‡
As noted above, it is usual to express the condition (X, Y) ∈ ‡K‡
by writing X :> Y in ‡G‡.
The immediate derivation relation is indicated by saying that
W “immediately derives” W', by saying that W' is “immediately
derived” from W in ‡G‡, and also by writing the following form.
• W ::> W'
A “derivation” in ‡G‡ is a finite sequence (W₁, …, Wₖ) of sentential forms
over ‡G‡ such that each adjacent pair (Wₕ, Wₕ₊₁) of sentential forms in the
sequence is an immediate derivation in ‡G‡, in other words, such that the
following holds.
• Wₕ ::> Wₕ₊₁ for all h = 1 to k-1
If there exists a derivation (W₁, …, Wₖ) in ‡G‡, one says that
W₁ “derives” Wₖ in ‡G‡ or that Wₖ is “derivable” from W₁ in ‡G‡
and one summarizes the derivation by writing the following.
• W₁ :*:> Wₖ
The language ‡L‡ = ‡L‡(‡G‡) = ⟨‡G‡⟩ generated by the formal grammar
‡G‡ = (“S”, ‡Q‡, ‡A‡, ‡K‡) is the set of strings over the terminal
alphabet ‡A‡ derivable from the initial symbol “S” by way of the
intermediate symbols in ‡Q‡ according to the characterizations
in ‡K‡. All that is summed up in the following form.
• ‡L‡(‡G‡) = ⟨‡G‡⟩ = {W ∈ ‡A‡* : “S” :*:> W}
Finally, a string W is called a “word”, a “sentence”, or so on,
of the language generated by ‡G‡ if and only if W is in ‡L‡(‡G‡).
Resources —
Generalities About Formal Grammars
• https://oeis.org/wiki/Cactus_Language_%E2%80%A2_Part_2
Survey of Animated Logical Graphs
• https://inquiryintoinquiry.com/2025/05/02/survey-of-animated-logical-graphs-8/
Survey of Theme One Program
• https://inquiryintoinquiry.com/2025/05/06/survey-of-theme-one-program-7/
Regards,
Jon
cc: https://www.academia.edu/community/lnaOK0
cc: https://www.researchgate.net/post/Generalities_About_Formal_Grammars
• https://inquiryintoinquiry.com/2025/07/03/generalities-about-formal-grammars-3/
Derivations —
An “immediate derivation” in ‡G‡ is an ordered pair (W, W′) of
sentential forms in ‡G‡ such that the following conditions hold.
• W = Q₁ ∙ X ∙ Q₂
• W' = Q₁ ∙ Y ∙ Q₂
• (X, Y) ∈ ‡K‡
As noted above, it is usual to express the condition (X, Y) ∈ ‡K‡
by writing X :> Y in ‡G‡.
The immediate derivation relation is indicated by saying that
W “immediately derives” W', by saying that W' is “immediately
derived” from W in ‡G‡, and also by writing the following form.
• W ::> W'
A “derivation” in ‡G‡ is a finite sequence (W₁, …, Wₖ) of sentential forms
over ‡G‡ such that each adjacent pair (Wₕ, Wₕ₊₁) of sentential forms in the
sequence is an immediate derivation in ‡G‡, in other words, such that the
following holds.
• Wₕ ::> Wₕ₊₁ for all h = 1 to k-1
If there exists a derivation (W₁, …, Wₖ) in ‡G‡, one says that
W₁ “derives” Wₖ in ‡G‡ or that Wₖ is “derivable” from W₁ in ‡G‡
and one summarizes the derivation by writing the following.
• W₁ :*:> Wₖ
The language ‡L‡ = ‡L‡(‡G‡) = ⟨‡G‡⟩ generated by the formal grammar
‡G‡ = (“S”, ‡Q‡, ‡A‡, ‡K‡) is the set of strings over the terminal
alphabet ‡A‡ derivable from the initial symbol “S” by way of the
intermediate symbols in ‡Q‡ according to the characterizations
in ‡K‡. All that is summed up in the following form.
• ‡L‡(‡G‡) = ⟨‡G‡⟩ = {W ∈ ‡A‡* : “S” :*:> W}
Finally, a string W is called a “word”, a “sentence”, or so on,
of the language generated by ‡G‡ if and only if W is in ‡L‡(‡G‡).
Resources —
Generalities About Formal Grammars
• https://oeis.org/wiki/Cactus_Language_%E2%80%A2_Part_2
Survey of Animated Logical Graphs
• https://inquiryintoinquiry.com/2025/05/02/survey-of-animated-logical-graphs-8/
Survey of Theme One Program
• https://inquiryintoinquiry.com/2025/05/06/survey-of-theme-one-program-7/
Regards,
Jon
cc: https://www.researchgate.net/post/Generalities_About_Formal_Grammars
Reply all
Reply to author
Forward
0 new messages