### Speculative Physics

## Symbols and Machines: Formal Languages and RPGs

**by Mendel Schmiedekamp**

Jan 21,2005

### Symbols and Machines: Formal Languages and RPGs

In the previous two articles, I discussed natural and computational languages, respectively. Even more abstract than computational languages are mathematical languages, also known as formal language. While natural languages are largely based on range of meaning and computational languages on precision of meaning, mathematical languages do no require a meaning at all. Rather formal languages give us tools for investigating the structure of language and information.

#### Mathematics of Language

In looking at languages from a formal perspective the idea of what a language consists of is greatly simplified. The first element to build this type of language is the **alphabet** which is a set of unique symbols. While it is easy to think of these symbols as letters, it often makes more sense to think of alphabets as the vocabulary of the language. Each symbol is intended to represent some atomic thing. By chaining these symbols into a sequence we can construct a word. A language is simply a set of words from an alphabet. From an RPG perspective, symbols can be construed as events and actions occurring in play, and words as sequences of these events and actions. In this way, a language and an RPG have a very direct relationship.

While words are all of finite length (infinite words can be used, but it requires much more care), there is no upper bound on how long a word can be, just as in an English sentence. This means that a set of words, i.e. a language, need not be finite, e.g. the language of English sentences. While it is possible to simply list the words of a finite language, for an infinite language we require the use of other tools to describe them. Two of the most common tools for this purpose are grammars and machines.

#### Grammars and Machines

A mathematical grammar is a set of rules used to construct words in a language. These rules usually take the form of translations. An initial starting symbol can be translated by sequential applications of different rules to construct a word. By making different choices in which rules to apply, and in what order, all the words in the language can be generated. One of the advantages of a grammar definition for a language is that it describes intrinsic structure of the language, making it easy to say, for example, that English sentences have a predominantly *subject verb object* structure.

While a grammar is useful to construct words in a language, it is often difficult to use a grammar to distinguish words in the language from those which are not. For the purposes of recognizing a language, the preferred model is that of a mathematical machine. One of the simplest types of machines is the finite automata, which I discussed last year here. Other types of machines can contain additional memory structure or more complex dynamics. The structure of the machine essentially maps out a procedure by which you can identify a word in the language by a series of (perhaps unending and often nested) tests. If the word ends having passed a test, it is recognized as a member of the language.

Most RPGs seem to act as combinations of grammars and machines. In some contexts during play, the only constraint is recognized boundaries, which identify when things are within the basic setting and system. On the other hand, at specific times, the system will become much more constrictive, usually when fairness or tactical interest are expected to heighten. Combat is by far the most typical example of this, but other situations, from inventing new technology to seduction have been treated this way. In this case, the RPG turns to a constructive approach, delineating specific options and building a series of possible decisions. Often an RPG is considered rules light or heavy based on whether it is primarily recognizing or constructing in nature.

#### Chomsky Hierarchy

While some languages and properties are easier to express with grammars or with machines, both tools can be used to describe any language. As these tools get more complex, there are natural hierarchies of types of grammars and machines. One of the most influential of these is the Chomksy hierarchy, which is both a hierarchy of grammars and machines. The Chomsky hierarchy uses the idea that a type or class of a grammar is based on the restrictions we place on its rules and the type or class of a machine can be based on the kind of memory it uses.

**Regular Grammars and Finite State Machines:** This class of languages is called the regular languages and is one of the simplest classes of language. A regular grammar is made of rules which produce exactly one final symbol at a time, and do not use any context. A finite state machine uses only transitions, and doesn't have any additional memory. This class of languages relates to the simplest and most constraining of systems. These games play like read-your-own-adventure books or more traditional styles of games. What is important however is that these games possess only a limited awareness of the current situations, if at all.

**Context Free Grammars and Push Down Automata:** The context free languages are more powerful than regular ones, but are still limited by a lack of long term information. Context free grammars again do not employ the context of their translations, but are otherwise unrestricted. Push down automata are finite state machines with a stack memory structure added to them. These games possess significant flexibility, represented by the idea of scopes, where some events may cause a narrowing of scope, which will then return to the previous scope after being handled. Whether this is wandering breaking to combat breaking to a maneuver breaking to a dice system, this sense of Last In, First Out can often be found in more structured games.

**Context Sensitive Grammars and Linear Bounded Automata:** A context sensitive language is a language which is powerful and at the same time relatively easy to understand. A context sensitive grammar is one which can take into account the context of each translation, but cannot delete symbols during translation, in essence each rule leaves some sort of mark. A linear bounded automata is a finite state machine which is essentially allowed to rewrite the paper on which a word is given it to recognize. These games are typically the most flexible and most complicated. This complexity often comes from keeping track of multiple situations at the same time or rewriting pasts to better fit current events. Many games simply incorporate a small amount of global context, rather than exploring the full possibilities and headaches of letting the entire game be rewritten at any time.

**Unrestricted Grammars and Turing Machines:** These languages are called recursively enumerable, and are the largest class of languages you usually want to consider. As fits the name an unrestricted grammar allows any sort of translation rule. Also a Turing machine is a finite state machine with no limit on the amount of "scratch paper". A game which incorporated the flexibility of a Turing machine would essentially build an entire hypothetical world or consider a vast number of future possibilities, simply to decide if a sword would hit a target or a character to make a statement. Such a system is likely far to cumbersome to permit a person to play it for very long, but as always the potential remains.

**Next Month:** Role, Play, and Game

### What do you think?

Go to forum!\n"; $file = "http://www.rpg.net/$subdir/list2.php?f=$num"; if (readfile($file) == 0) { echo "(0 messages so far)"; } ?>

### Previous columns

- Testing the Boundaries II - Putting Things Together by Mendel Schmiedekamp, 28dec05
- Testing the Boundaries I - Taking Things Apart by Mendel Schmiedekamp, 29nov05
- Need for Speed by Mendel Schmiedekamp, 21oct05
- Groups Redux by Mendel Schmiedekamp, 23sep05
- Two for One by Mendel Schmiedekamp, 19aug05
- Death of Culture by Mendel Schmiedekamp, 27jul05
- Zero Sum by Mendel Schmiedekamp, 17jun05
- Technobabble by Mendel Schmiedekamp, 17may05
- Constrained by One Another by Mendel Schmiedekamp, 22apr05
- Patterns and Play by Mendel Schmiedekamp, 18mar05
- Role, Play, and Game by Mendel Schmiedekamp, 18feb05
- Symbols and Machines: Formal Languages and RPGs by Mendel Schmiedekamp, 21jan05
- Form and Meaning: Computational Languages and RPGs by Mendel Schmiedekamp, 23dec04
- Growing Games: Natural Language and RPGs by Mendel Schmiedekamp, 19aug04
- Speaking in Tongues by Mendel Schmiedekamp, 21jul04
- Planning for Failure by Mendel Schmiedekamp, 20may04
- Between the Steps by Mendel Schmiedekamp, 23apr04
- The Road Once Traveled by Mendel Schmiedekamp, 24feb04
- Seeds of Enlightenment by Mendel Schmiedekamp, 30jan04
- Mathematics of Game Design: Probability and Statistics by Mendel Schmiedekamp, 23dec03
- Mathematics of Game Design: Game Theory and Related Concerns by Mendel Schmiedekamp, 31oct03
- Mathematics of Game Design: More Finite Structures by Mendel Schmiedekamp, 24sep03
- Mathematics of Game Design: Finite Structures by Mendel Schmiedekamp, 29aug03
- Homeworld Project 2: Modes, Grains, and Journeys by Mendel Schmiedekamp, 28may03
- The Homeworld Project by Mendel Schmiedekamp, 30apr03
- Desk Juggling: Designing Players and the Statistical Metagame by Mendel Schmiedekamp, 26mar03
- Juggling Desks: Balance and Dice by Mendel Schmiedekamp, 29jan03
- Fuzzy Alchemy by Mendel Schmiedekamp, 30dec02
- The Opposition Rests by Mendel Schmiedekamp, 27nov02
- A Brief Introduction by Mendel Schmiedekamp, 28oct02

### Other columns at RPGnet

TQo0~^DҒt< ek&Ǿ$\۵ZFȃuwݝIŃU QYir2HR2.u3MFoعq]4#A`pP5(b&)b)ⰾp7(i<[-2gL#5[f g?*rVGf8*)s'+20ϟ̑F}KB<7wSL\gbvm9WiRބYŜvdy0'p2I_Fc2>#oA )VL[Qk?3`)<У[(*W.JH ?tXCt谙 X:@ \0w~LqĤE-rFkYj4q 5AQ6[AxG [>w|?( fХθY䝛$c=_qNĦoǸ>O_|&/_Mi7"宥CЧk0dӷLh;TmuCGU-!Ul{ h<\bQX.~"O2*yPcz!Gg