Words & Parallel Universes

Yamac Eren Ay
9 min readMay 12, 2022
Source: https://chemical-collective.com/de/blog/Was-ist-1cp-LSD%3F-Was-sind-seine-Auswirkungen-und-wo-kann-ich-es-kaufen/

Let’s assume, a word in a parallel universe looks like a tree of letters instead of a sequence, and we cannot enumerate the letters in words anymore. Ask yourself these questions:

  • How different would the languages look like?
  • How much more complex would be the algorithms?
  • How could books adapt to the change?
  • What would be the consequences?

In the following sections, I will introduce some of the concepts from the formal languages & automata, then re-define and analyze the grammar types.

Introduction to Formal Languages & Automata

If you don’t understand the concepts, you can find additional sources at the end.

Important Definitions

Alphabet: A set of letters Σ = {a_{1}, …, a_{m}}. Each letter stands for a value.

Word: A sequence of letters w = (w_{1}, w_{2}, …, w_{l}) or simply w_{1} w_{2} … w_{n}, where ∀ i ∈ {1, …, l} . w_{i} ∈ Σ. Each word stands for an argument.

Language: A set of words. Each language stands for a problem, which accepts / rejects words.

Grammar: Basically a set of rules and letters, which define the syntax of a language. It can create any word in a language. Two types of grammars worth considering in this article:

  • Regular (or type-3) grammar: It can create a word from left to right*[1] (1 direction)
  • Context-free (or type-2) grammar: can create a word in both directions (2 direction)

Automaton: Similarly a set of states and letters, which define the syntax. It accepts the words of a language, and rejects other words.

Word Problem: The algorithmic problem of whether a word is accepted by a language. In general, word problems can be solved using top-down recursive formulas*[2]. If root node satisfies the criteria, the word is included in the language.


*[1]: There are left-regular grammars which can work in reverse direction, each forms a reverse language of a right-regular language, so each grammar can be represented by right-regular grammars.

Yamac Eren Ay

I love to write articles about the most underrated topics in computer science