Question about CFGs: || kuro5hin.org


	create account \| help/FAQ \| contact \| links \| search \| IRC \| site news

Everything

We need your support: buy an ad | premium membership | k5 store

Question about CFGs: (Diaries)

By llimllib
Wed Feb 19th, 2003 at 08:10:15 PM EST

I was reading my programming languages textbook, which was talking about context free grammars, and specifically about ambiguity in context free grammars. It mentioned in passing that a given example was unambiguous, but that the proof was out of the scope of the book. Since then I've tried googling for the answer, with no luck.

Anyone know how to prove that a CFG is unambiguous?

Sponsors

Managed Servers
Managed Clusters
Virtual Hosting

Collocated Linux/FreeBSD Server
As low as $45/month

Root on your own FreeBSD or Linux server

Very fast, triple-homed network

NO hardware or setup fees, unlimited support

Testimonials from K5 Users

Login

Make a new account

Username:

Password:

Note: You must accept a cookie to log in.

Related Links

llimllib's Diary

View: Display: Sort:

Question about CFGs: | 3 comments (3 topical, 0 editorial, 0 hidden)

a little secret about computer science (none / 0) (#3)
by turmeric on Wed Feb 19th, 2003 at 09:57:49 PM EST

there is so much shit to prove that , generally, given some theorem or something, only about 0.01 % of the CS populace has ever even looked it up, let alone taken the time to understand it (that LaTeX makes readable publications really impossible)

but don't go too far into this 'looking up the proof' business, you might find , in fact, that we don't really know a whole hell of a lot. once u realize all of CS relies on godel's incompleteness theorem you are pretty much hosed, because how can you reconcile the fact that all logical systems have truth that cant be proven, with the dogmatists that run our military industrial establishment? godels theorem relegates our entire ideas of obedience and 'chain of command' and 'ours is not to reason why' to the ashbins of philosophical history.

no no no. what you want to do is stick to something like optimization theory. enough of this proof garbage. leave it to the wackos in the philosophy department.

there's no good way to do it (none / 0) (#2)
by Delirium on Wed Feb 19th, 2003 at 09:55:40 PM EST
(delirium-k5@rufus.d2g.com)

To prove a grammar is ambiguous, you simply need to find a single string with two valid parse trees. To prove a grammar is unambiguous, on the other hand, you need to prove that every possible syntactically valid string in the language has exactly one parse tree. IIRC, this is impossible in the general case, but possible if there are either a finite number of strings, or an infinite number of strings with some regular properties (i.e. there's a finite number of non-repeating strings, and the rest are simply repeating versions of them, or something like that).

Read my diary.

Hm... it's been a while (none / 0) (#1)
by fluffy grue on Wed Feb 19th, 2003 at 08:57:32 PM EST
(magenta at trikuare dot cx) http://trikuare.cx/

It's been a while since my 'theory of computation' class, but I believe that the way you prove the unambiguity of a language is by showing that there's no two subrules which can generate the same expression, and this is done with some rather simple logic by breaking all the rules down into subrules each of which forms one input and two outputs.

Unfortunately, I lent my textbook for that class to an officemate, who later 'returned' it to me by placing it on the communal table in the middle of the office and forgot to let me know that he'd "given" it back, and someone else walked off with it.
--
"Is not orange" is not orange.
"Is not a quine" is not a quine.

Cats: Nature's entropy generators

[ Hug Your Trikuare

Question about CFGs: | 3 comments (3 topical, 0 editorial, 0 hidden)

View: Display: Sort:

All trademarks and copyrights on this page are owned by their respective companies. The Rest � 2000 - 2003 Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
Erik Benson is a deadbeat.