K,
just have some thoughts / questions on the first part of the work. you might find another post after this touching on other topics.
please give your input.
The Theorem that allows you to see if language is finite / infinite:
My understanding according to theorem 43 and 44.
0. make sure is isn't nullable, byt reverse working the NULL sign to see if S ever gets to NULL.
Question: if its NULLABLE, what does this mean? surely there are ways to make S -> Null, but that doesnt mean we dont have other ways of generating words.
1. make sure its in CNF
2. remove unproductive terminals (ones that dont go to nonterminals ever -- ie. N =>* n - it will never reach n)
3. Find the useful ones by blue paint. The we know which Non terminals take part in forming words. Remember the useful ones;
4. show that the useful non terminals are actually usefull by substitution
5. Now mark each of the useful NON Terminals as FUNNYX, and see if its self embedded.
IF USEFULL and SELF EMBEDDED then L = INFINITE
Missing anything
Danie van Eeden
------------------------
