singularity

singularity 🔎

#learnings

Build Your Own Lisp, Chapter 5

Chomsky Hierarchy

• there are formal grammars -> rules of logic arranged in a (highly) relational order
  • the relation is that of 'containment' / sets, these rules form sets and have subsets (of other rules)
  • the overall grammar is a finite set
  • the rules are called 'production rules [PR] -> they produce ‘states’ -> LHS -[PRoduces]-> RHS
    • as such possibly these rules can be thought of as functions

LHS -[produces]-> RHS

• both sides are finite sets constituting
  • finite set of nonterminal symbols = some PR can yet be applied
  • finite set of terminal symbols = NO PR can be
  • 🚗 a start symbol

Formal Grammar

• provides (generates) axiom schema FOR a formal language
• More here: https://en.wikipedia.org/wiki/Chomsky_hierarchy

Chomsky Hierarchy of Grammars and Languages

• The grammar for any given set is, however, usually far from simple. (We say "The grammar for a given set” although there can be, of course, infinitely many grammars for a set. By the grammar for a set, we mean any grammar that does the job and is not obviously overly complicated.)
• Theory says that if a set can be generated at all (for example, by a program) it can be generated by a phrase structure grammar, but theory does not say that it will be easy to do so, or that the grammar will be understandable.
• In this context it is illustrative to try to write a grammar for those Manhattan turtle paths in which the turtle is never allowed to the west of its starting point (Problem 2.3).
• Apart from the intellectual problems phrase structure grammars pose, they also exhibit fundamental and practical problems. We shall see that no general parsing algorithm for them can exist, and all known special parsing algorithms are either very inefficient or very complex; see Section 3.4.2.
• The desire to restrict the unmanageability of phrase structure grammars, while keeping as much of their generative powers as possible, has led to the Chomsky hierarchy of grammars.
• This hierarchy distinguishes four types of grammars, numbered from 0 to 3; it is useful to include a fifth type, called Type 4 here.
• Type 0 grammars are the (unrestricted) phrase structure grammars of which we have already seen examples. The other types originate from applying more and more restrictions to the allowed form of the rules in the grammar.
• Each of these restrictions has far-reaching consequences; the resulting grammars are gradually easier to understand and to manipulate, but are also gradually less powerful. Fortunately, these less powerful types are still very useful, actually more useful even than Type 0.
• We shall now consider each of the three remaining types in turn, followed by a trivial but useful fourth type. For an example of a completely different method of generating Type 0 languages see Geffert [395].

---

A Chomsky grammar is a finite mechanism that produces a usually infinite set of strings, a “language.” Unlike many other set generation mechanisms, this production process assigns a structure to the produced string, which can be utilized to attach semantics to it. For context-free (Type 2) grammars, this structure is a tree, which allows the semantics to be composed from the semantics of the branches. This is the basis of the importance of context-free grammars.

---

TYPE 0 GRAMMARS - REGULAR

TYPE 1 GRAMMARS - CONTEXT FREE

TYPE 2 GRAMMARS - CONTEXT SENSITIVE

TYPE 3 GRAMMARS - RECURSIVELY ENUMERABLE

TYPE 4* GRAMMARS - FINITE CHOICE GRAMMAR

2.6 Grammars that Produce the Empty Language 2.7 The Limitations of CF and FS Grammars

---

1. By J. Finkelstein - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=9405226