The Program:

When I enter production rules, I might have a rule S -> e , but, if I do, that will be the only time the empty string appears in a rule.

I will also never have S in the right side of a production rule.

This means a couple of things:

1.  If S->e is a rule, then the language accepts the empty string.  If S->e ain't in there, then the language does not accept the empty string.  You do not need to run the algorithm to check the empty string case.

2.  S->e is not a rule you ever need to apply backwards in your algorithm.  In fact, the algorithm sucks if you do.  Or, put another way, you suck if you do.

S->e  S->T   T->TT  T->(T)  T->()   [Balanced parentheses]

The whole point of context-sensitive grammar recognition is that your string should never get longer.

(()())


(T())*
(()T)*
(S())*
(TT)*
(()S)*
(ST)*
(TS)*
(T)*
(SS)*
T*
S
())*
T)*
S)*

At every step, you dequeue a string try all possible backward replacements EXCEPT S->e and enqueue the new string UNLESS you've used that one before.  Keep track of the ones you've already seen! (HashMap, perhaps?)

If you ever get S, you're done, it's in the language.  If the queue is empty and you still haven't found S, you're done, it's not in the language.

Since the grammar is context sensitive, the strings you enqueue will never be longer than the strings you dequeue.

The set of strings representing the first ten trillion prime numbers.

This is regular.  Just work out the first ten trillion primes...and stick ors in between them.

The set of strings representing all prime numbers.

Not regular.  Can't be done.  We can prove this using...THE PUMPING LEMMA

ALL finite sets of strings are regular.

Most infinite sets of strings are not.

Balanced parentheses:  not regular.

Remember what NP is:

NP is a class of languages that can be recognized by nondeterministic Turing machine in polynomial time.  Meaning that if the answer is YES, there is a path through the NTM that will return YES in more than p(n) steps where p is a polynomial and n is the length of the input.  (If the answer is NO, machine infinite loops.)

Traveling Salesman, Partition, Vertex Cover, Clique, Hamiltonian Cycle.  These can easily be solved in polynomial time on a nondeterministic Turing Machine.

We have a similar class of problems called co-NP.  These are problems phrased the opposite way.  If the answer is YES it infinite loops.  If the answer is NO there is a path through the NTM that determines NO and halts in p(n) time.

Does NP equal co-NP?  Unsolved problem.

co-NP = { SIGMA* - L : L is a language over the alphabet SIGMA and L is in NP }

If there exists an NP-complete problem PI such that PI-complement  is in NP, then NP = co-NP.

Oracle Machines aka Oracle Turing Machines

An Oracle Machine is like a Turing Machine but it has a second tape, an "oracle tape."  The oracle tape has its own tape head.  You can either head left or right, you can write on either tape any time you like, you can examine any tape any time you like.  BUT, the Oracle Tape has an ASK function. When you execute the ASK command.  The oracle tape has a fixed pre-programmed machine attached to it.  When you issue ASK, the information on the Oracle Tape is treated as input, it is immediately replaced with output determined by the oracle, and then this output can be used.

The oracle is immediately replaced with output.  It's not placed there by another Turing Machine.  The output is said to happen in one step.  Ain't no law that says the oracle is restricted to the normal laws of computing.

For example, the oracle might solve the Halting Problem.  Your Turing  Machine writes the encoding of another Turing Machine plus input that that Turing Machine is to be given, asks the Oracle.  The oracle immediately erases the tape and replaces it with YES or NO depending on whether that Turing Machines halts on that input.

Thus if you have an Oracle machine programmed with the Halting Problem, you now have a whole class of problems you can solve.  [You can use it to prove the twin prime conjecture.  You can use it to find unreachable code in a computer program.]  You can do all sorts of things when you are not constrained by reality.