Regular and Context Free Languages

A language is set of strings, formally.
Any Java program is a string of characters that the Java Virtual Machine recognizes as vaild syntax, for example.

A Regular Expression is a way to classify an acceptable pattern.  

In Computer Science, a pattern involves:
Concatenation (usually done by putting one after the other)
Alternation (a.k.a. ‘OR’) (usually done with ‘|’)
Grouping (usually done with parenthesis)
Quantification:
	? typically means 0 or 1 occurrences
* Means 0 or more occurrences
+ means 1 or more occurrences

So, for example:
(0 | 1) * 111 (0 | 1) * means any string that has three ones in a row

Formally, given an alphabet, and an expression consisting of concatenation, alternation, and quantification (* is the only quantification symbol that is actually needed),
A Regular Language is the set of strings using that alphabet, that follows the given rules.

For further information, see:
Regular expression - Wikipedia
https://www.cs.odu.edu/~zeil/cs390/latest/Public/fsa/index.html

Regular expressions show up in Computer Science all of the time.

Most simple electronic circuits can be represented by a regular expression.
For example, light bulb L is on if:
(A | B) C
(A or B is on, and then C is on)

It is also possible to represent regular expressions by a diagram:

This is a diagram that accepts any (binary)string that has three ones in it, total.
(0)* 1 (0)* 1 (o)* 1 (0 | 1)*

This represents the diagram of a very simple vending machine.  
It accepts nickels, dimes, or quarters.
In such diagrams, there is a start state, and one or more accepting states.
If there are loops, that involves * (quantification)

In words, once you have accumulated 25 cents of nickels, dimes, or a quarter, you win a prize.
(NNNNN | DNNN | NDNN | NNDN | NNND |DDN | DND | NDD | Q) might be a regular expression.

So why is this important for game design?
What happens in combat can often be represented as a Regular Expression.
(The states in a diagram may represent hit points left, for example.)
Maps and Mazes (such as in Adventure) can be represented as a regular expression.

The applications are endless.

However, Regular Expressions, which are equal in power to Finite State Automata, are actually very limited.  For example:
(a)* (b*) represents any number of ‘a’s, followed by any number of ‘b’s, is fine.
But it is NOT POSSIBLE to say:
A language consisting of all strings which have:
N ‘a’s, followed by N ‘b’s.
(a)N (b)N, which would allow ab, aabb, aaabbb, and so on, CANNOT be described by a regular expression.  The proof of it is beyond this class, but is discussed at:
https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

A regular expression, represented by either a regular expression, or a Finite State Diagram (see above) represents a certain CLASS of languages.
(It turns out that a non-deterministic regular language is actually the same class, but let’s not worry about that.)
Nondeterministic finite automaton - Wikipedia

The next ‘level up’ is a Context Free Language.
In a Context Free Language, you do have a very limited sort of memory.
In essence, you have a Stack available.
https://en.wikipedia.org/wiki/Context-free_grammar
https://en.wikipedia.org/wiki/Chomsky_normal_form
https://en.wikipedia.org/wiki/Noam_Chomsky

Most modern compilers are written by first designing a Context Free Grammar for the language.
(Elements, such as variable names, are often described by regular expressions.)
A Context Free Language can be recognized by a Push Down Automata, kind of like a regular expression, but in addition to input, you can push or pop items on a Stack.

Grammar rules can be useful in Game Design if you wish certain naming conventions, or want to design an actual language for your game.

Example Context free grammar:
S is a Sentence
N is a Noun
V is a Verb
A is an Adjective
D is an Adverb

S -> N V
N -> A N | N
N -> boy | girl | dog
V -> D V | V | V D
V -> run | walk | swim
A -> big | little
D -> fast | slow

These rules say:
A Sentence is a Noun followed by a Verb.
A Noun is either an Adjective followed by a Noun, a Noun, or a specific word that is a noun.
A Verb is either an adverb followed by a Verb, a Verb, or a specific word that is a verb.
So if you want to derive a ‘Sentence’ in this language, use the rules, start with S, and continue until every S,N,V,A,D is replaced by one (or more) words.
	S
	NV
	ANV
	ANDV
	big NDV
	big dog DV
	big dog fast V
	big dog fast run

Here is a GFG for generating names:
N Name
L syllable
C consonant
V vowel

//N -> LN  			//would give unlimited syllables
N -> LL | LLL | LLLL | LLLLL 	//all names have at least two syllables 
L -> V | CV | VC | CVC 		//a syllable has one vowel, and no two consonants are in a row
V-> aeiouy
C -> b...z

Is bigbigdoggydog a valid name?

bigbigdoggydog
cvc cvc cvc cvc vc
LLLLL
N

Beyond CFG, there are categories such as Turing Decidable, and Turing recognizable.
(A Turing machine is a hypothetical little robot that runs up and down a tape, making and erasing marks as it goes.  No modern computer is more powerful than a Turing machine!)
https://en.wikipedia.org/wiki/Turing_machine

There are also undecidable problems.  One example:
It is NOT POSSIBLE, in the general case, to write a program that can determine if an input program will correctly handle given input.  It is not even possible to determine, in the general case, to determine if a program will infinite loop or halt, on certain input.
I have known more than one employer to be very annoyed when they asked someone to write a program that was provably impossible to do!
Halting problem - Wikipedia