Welcome! Log In Create A New Profile

Advanced

Regular grammer - CFG

Posted by Japster 
Announcements Last Post
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
Regular grammer - CFG
February 10, 2009 12:59PM
In Cohen on pg 264 the say that a CGF is called a regular grammer is each of its productions is of one of the following forms
Nonterminal -> semiword
Nonterminal -> word

Well what i want to know now is this; Does not all CFG's come in this format? Which would make them all regular languages?

Japster
Re: Regular grammer - CFG
February 12, 2009 05:44PM
Not every context-free grammar is a regular grammar.

From Wikipedia:
"A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. This restriction is non-trivial; not all languages can be generated by context-free grammars. Those that can are called context-free languages."

Also, not every RG is a CFG
Again from Wikipedia
"In regular grammars, the left hand side is again only a single nonterminal symbol, but now the right-hand side is also restricted. The right side may be the empty string, or a single terminal symbol, or a single terminal symbol followed by a nonterminal symbol, but nothing else."

So the example in Cohen is indeed both a CFG and a RG, but it is not always the case that a CFG is a RG.

It also is good to remember that every regular language is context free, but not every context free language is regular. (To prove that a context-free language is regular, you need to use the pumping lemma.)
Sorry, only registered users may post in this forum.

Click here to login