Welcome! Log In Create A New Profile

Advanced

Theorem for INFINITE LANGUAGE OR NOT

Posted by dve83 
Announcements Last Post
Announcement myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Theorem for INFINITE LANGUAGE OR NOT
October 22, 2011 04:17PM
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
------------------------
Sorry, only registered users may post in this forum.

Click here to login