# Theorem for INFINITE LANGUAGE OR NOT

Posted by dve83
Announcements Last Post
myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Theorem for INFINITE LANGUAGE OR NOT October 22, 2011 04:17PM Registered: 13 years ago Posts: 129 Rating: 1
K,

just have some thoughts / questions on the first part of the work. you might find another post after this touching on other topics.

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
------------------------
Sorry, only registered users may post in this forum.