x = (x * 32273) % 65537  //Pseudo-random generator

Take any integer from 1 to 65536, you get another number in that same range, and it will cycle through all of them before repeating.

It works because 65537 is a prime.  32273 is coprime to 65537 (duh, because is a prime), 32273 is called a generator of the multiplicative group modulo 65537.

65537 was chosen precisely because a) it's prime and b) it just happens to be equal to 2^16 + 1.  SO, if you need a random floating point greater than or equal to zero and less than one, take (x-1)/65536, and you cover the gamut of sixteen-bit floating point numbers (which in the 1980's, was quite reasonable).

But my random numbers were NOT the same, because the first one came from the system clock.

CHOMSKY NORMAL FORM

Every CFG can be written in Chomsky Normal Form.

Rules can be of the form:

A->BC   (where neither B nor C are the start state)
A->a    (a is a token in the alphabet)
S->e    (This is the only way to get the empty string into the language)

And you can convert any grammar to CNF, usually in about four steps (warning:  sometimes CNF grammar can be grossly larger than the original grammar).

1.  Eliminate the Start State from the right hand side
2.  Eliminate non-solitary tokens from the right hand side
3.  Eliminate those rules containing more than two nonterminals
4.  Eliminate nullables  (non-terminals that MIGHT go to the empty string)
5.  Eliminate unit rules (A->B, things like that)

S->SS
S->(S)
S->e

(Balanced parentheses)

1.  Eliminate the start symbol from the right side
S->T
T->TT
T->(T)
T->e
S->e

2.  Eliminate nonsolitary terminals

Get rid of rules that use terminals but in conjunction with other symbols.  In this case, there's only one rule that does that:  T->(T)

This is an easy problem to solve:  just make new rules for ( and )

S->T
T->TT
T->LTR
T->e
L->(
R->)
S->e

3.  Eliminate rules with more than two nonterminals

There is only one rules that violates this:  T->LTR

This is also an easy correction.

S->T
T->TT
U->LT
T->UR
T->e
L->(
R->)
S->e

Eliminate nullables, those symbols other than S, that can go to the empty string.  There are ways for a symbol to be nullable.

1.  A->e    there's some rule like this in which the left side goes directly to null.

2.  A->X1 X2 X3 ... Xn  where all of X1 ... Xn are themselves nullable.

So, in this case, there is only one nullable, T

Get rid of this by simply replacing T with e in the various rules.

S->T
T->TT
T->T
U->LT
U->L
T->UR
//T->e  We can delete this rule, it is no longer necessary.
L->(
R->)
S->e

Then, we get rid of the unit rules (A->B, just one thing on the right.)

We have two such rules:  S->T  and T->T  and U->L.  T->T is just stupid, so we can just drop that.

S->T can be replaced with S->TT and S->UR

S->TT
S->UR
T->TT
U->LT
U->L
T->UR
L->(
R->)
S->e

Eliminating U->L, we can replace that rule with U->(

S->TT
S->UR
T->TT
U->LT
U->(
T->UR
L->(
R->)
S->e

Anyway, this is Chomsky Normal Form.

Another normal form you sometimes see is Greibach Normal Form.

Every rule is of the form A->a A1 A2 A3 ... An .  In other words,
Every rules begins with one terminal and however many nonterminals you want after that.

Since this cannot generate the empty string, sometimes you'll see the same sort of alterations made to that as you see with CNF (the start can't appear on the right, and S->e is a valid rule.)

GNF is used (has been used) by some parsers.  If you're trying to see whether a string in the language.  You know the first character of the string.  If a string with a, then you really need to start with S->a ...
If there is no such rules, then the string isn't in the language, but if there are such rules, then you use these to decide what rules need to process the second character and so on.

1 S->(TR
2 T->(TR
3 T->(R
4 T->(TRT
5 T->(RT
6 R->)
7 S->e
8 S->(R

So, if I'm looking at (()), the initial left parenthesis tells me I must apply rule 1 or rule 8.

So then looking at ()),  with rule 1 and rule 8 being the only rules I can apply  Can R be applied to a string beginning with ( (no) so rule 8 is out.  Can T be applied to a string beginning with ( (yes) so rules 2, 3, 4, 5 are valid next steps.

Applying 2, 3, 4, 5 to )), we see that T can't begin with a ), eliminating rules 2 and 4.  But R can begin with a right ), so 3 and 5 are valid for the next step.

Apply 3 and 5 to ).  3 is the rules that applies because rule 3 has nothing nothing following the R (rule 5 does).

This can all be handled iteratively, without recursion.

PUSHDOWN AUTOMATA.  This is the theoretical machine that accepts context-free languages.  These automata are nondeterministic unless otherwise specified, because deterministic PDA's are not powerful enough to accept all context-free languages.

You can think of PDA as having having a set of states and transitions must like a finite automaton, but you also have access to a stack and you can put as much on the stack as your want, but you only have access to the top element.  You can't see what's below the top element unless you pop (and discard) the top element.