Prev: Is your computer safe and secure!
Next: Integer factorization, etc.
From: sidgalt on 2 Apr 2008 00:51
Hi,
Is there a way formally state in first-order logic that an arbitrary
grammar is unambiguous?

If so then could we run two algorithms in parallel - one which
searches for an ambiguity in a grammar and the second which searches
for a proof that the specified grammar is unambiguous. Both problems
are undecidable but
since a grammar has to be either ambiguous or unambiguous, atleast one
of the algorithms must always halt thus giving a way to always answer
the question whether a given grammar is unambigous or ambiguous.

Thanks
Sid
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen on 2 Apr 2008 04:59
"sidgalt(a)gmail.com" <sidgalt(a)gmail.com> writes:

> Is there a way formally state in first-order logic that an arbitrary
> grammar is unambiguous?
>
> If so then could we run two algorithms in parallel - one which
> searches for an ambiguity in a grammar and the second which searches
> for a proof that the specified grammar is unambiguous. Both problems
> are undecidable but
> since a grammar has to be either ambiguous or unambiguous, atleast one
> of the algorithms must always halt thus giving a way to always answer
> the question whether a given grammar is unambigous or ambiguous.

So I guess, since the problem is known to be undecidable, that you
have just now proven that there can't be a first-order statement of
unambiguity.

Torben
From: tchow on 2 Apr 2008 10:05
In article <2328c9b5-0f33-492d-bb0b-ce54b3cf7a00(a)n58g2000hsf.googlegroups.com>,
sidgalt(a)gmail.com <sidgalt(a)gmail.com> wrote:
>Is there a way formally state in first-order logic that an arbitrary
>grammar is unambiguous?

What first-order language specifically are you asking about? It's certainly
possible to state this in the first-order language of set theory, just as
almost any mathematical statement can be stated in the first-order language
of set theory.

>If so then could we run two algorithms in parallel - one which
>searches for an ambiguity in a grammar and the second which searches
>for a proof that the specified grammar is unambiguous.

The problem is that the grammar might be unambiguous but there might not
be any *proof* that it is unambiguous.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
 | 
Pages: 1
Prev: Is your computer safe and secure!
Next: Integer factorization, etc.