[Tutor] Automaton/transitional grammar query

[Kent Johnson]

On Mon, Oct 12, 2009 at 10:47 AM, Kent Johnson <kent37 at tds.net> wrote:
> On Mon, Oct 12, 2009 at 10:09 AM, kevin parks <kp8 at mac.com> wrote:

>> Yeah i don't mean an infinite loop, but more like a perpetual dance back and
>> forth between to items
>> that point to each other. I think I need to be careful when i define the
>> rules that i don't get something like that... say if 1 goes to 4 but 4's
>> rule is go to 1, for example.
>
> That can clearly happen. There are several cases:
<snip>
> - at least one rule, but not all, maps to more than one symbol. In
> this case either outcome is possible, depending on whether the
> expanding rule is repeatedly hit.

If you consider the set of rules as a directed graph, the question
becomes something like, does the graph contain any cycles which
- contain rules that map to more than one symbol, and
- are reachable from the start symbol

I'm not sure but I think there are probably standard methods of graph
theory to answer this question.

Kent