Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| Regular grammar from CFG? netsch@ti.com (Lorin Netsch) (2004-09-03) |
| Re: Regular grammar from CFG? newsserver_mails@bodden.de (Eric Bodden) (2004-09-07) |
| Re: Regular grammar from CFG? vannoord@let.rug.nl (2004-09-07) |
| Re: Regular grammar from CFG? brosgol@worldDOTstd.com (Ben Brosgol) (2004-09-08) |
| Re: Regular grammar from CFG? vbdis@aol.com (2004-09-08) |
| Re: Regular grammar from CFG? friedrich.neurauter@eunet.at (Friedrich Neurauter) (2004-09-08) |
| Re: Regular grammar from CFG? cdc@maxnet.co.nz (Carl Cerecke) (2004-09-08) |
| Re: Regular grammar from CFG? neal.wang@gmail.com (2004-09-13) |
| [1 later articles] |
| From: | Eric Bodden <newsserver_mails@bodden.de> |
| Newsgroups: | comp.compilers |
| Date: | 7 Sep 2004 23:50:39 -0400 |
| Organization: | RWTH Aachen University |
| References: | 04-09-035 |
| Keywords: | parse, theory |
| Posted-Date: | 07 Sep 2004 23:50:39 EDT |
Hi, Lorin.
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
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.
- A -> Ba The same.
... 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.
Eric
--
Eric Bodden, ICQ: 12656220, http://www.bodden.de, PGP: BB465582
Active Desktop Wallpaper Changer: That's what it is...
http://bodden.de/projects/wpchanger/
Return to the
comp.compilers page.
Search the
comp.compilers archives again.