Re: Regular grammar from CFG?

"Friedrich Neurauter" <>
8 Sep 2004 12:05:49 -0400

          From comp.compilers

Related articles
Regular grammar from CFG? (Lorin Netsch) (2004-09-03)
Re: Regular grammar from CFG? (Eric Bodden) (2004-09-07)
Re: Regular grammar from CFG? (2004-09-07)
Re: Regular grammar from CFG? (Ben Brosgol) (2004-09-08)
Re: Regular grammar from CFG? (2004-09-08)
Re: Regular grammar from CFG? (Friedrich Neurauter) (2004-09-08)
Re: Regular grammar from CFG? (Carl Cerecke) (2004-09-08)
Re: Regular grammar from CFG? (2004-09-13)
Re: Regular grammar from CFG? (2004-09-13)
| List of all articles for this month |

From: "Friedrich Neurauter" <>
Newsgroups: comp.compilers
Date: 8 Sep 2004 12:05:49 -0400
Organization: Compilers Central
References: 04-09-035 04-09-042
Keywords: parse, theory
Posted-Date: 08 Sep 2004 12:05:49 EDT

"Eric Bodden" <> schrieb

> On 3 Sep 2004 12:42:40 -0400, Lorin Netsch wrote:
> > Can anyone tell me how to determine if a given CFG can be represented
> > as a regular grammar?
> I believe there can be no way to do so, since I think, there is no way
> to convert a grammar that is more than regular to one that is regular.
> That is due to the Chomsky hierarchy. Type-3 grammars (regular ones)
> are strictly weaker then Type-2 and so forth.
> Regular grammars allow rules of the types
> A -> aB
> A -> a

This is not quite correct. Take a look at the definitions of left linear,
right linear, strongly left linear and strongly right linear grammars

> Now just imagine the possible productions of a grammar that is not yet
> regular:
> - A -> B This cannot be represented by a rule of the ones above.

But this is a so called unit production which can be easily removed from
any grammar without changing the generated language.

> - A -> Ba The same.

In a left linear grammar productions like this are allowed and yet left
linear grammars generate regular languages

> ... and so forth.
> So in my eyes either a grammar is already regular or it is not. And if it
> is not it will never be. Please correct me, if I am wrong.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.