*A problem we hit while working on CLOPS. We know
a good solution but it makes a nice puzzle.*

**Problem.** A digraph has letters on edges, so there is a word
corresponding to each walk. Given two nodes *m* and *n*, are there two distinct walks
*m* ↝ *n* that have the same corresponding word?

**Examples.** We are looking at walks from blue
to red.

In the graph

there are no two distinct walks with the same word.

If the graph

has the letter *x* on all edges then there are two distinct walks
corresponding to the word *xxxxxxxxxxxxxxxxx* (length 17).

**Comment.** This problem amounts to finding whether a
CLOPS input file, which is a regular grammar for what can go
on the command line of a program, is ambiguous.

## 13 comments:

Hi rgrig :).

Is this problem in some online judge to test my possible solution?

Thanks.

I was planning to add it to SPOJ. I'll try to do it today now that you asked.

It's problem AMBIG. I think the tests could be better. Let me know if you have any interesting cases that I should add.

Thanks for uploading the problem, I managed to solve it :).

About this case:

2 2

0 1 0

0 1 0

The answer is YES, right?

That's one the tests. :)

I supposed that. What about this one?

2 3

0 1 0

1 0 1

1 0 1

I think the answer should be YES.

If you meant "3 2" (3 edges, 2 nodes) instead of "2 3" then I agree. I added it as a test. Thanks.

Yes, I meant that, 3 edges, 2 nodes.

You are welcome.

What is the name of algorithm that solves this?

Thanks.

It's a slightly modified version of automata intersection.

The problem appears in a research paper from 1965:

S Even, On Information Lossless Automata of Finite Order.

i tried to submit solution spoj.

i am getting wrong answer. is there any corner cases to consider?

Thanks

solved thanks

i was solving the problem on spoj,it gives wrong answer in 16th-17th case,any corner case to consider?

here is my solution http://ideone.com/084uqo

any place where i can learn the algo to check ambiguity,like in this problem?

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.