most recent 30 from http://mathoverflow.net 2013-05-25T07:58:23Z http://mathoverflow.net/feeds/question/71158 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71158/transition-graph-per-alphabet trentonknight 2011-07-24T22:12:13Z 2011-07-24T23:10:53Z

<p>How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from Daniel I. A. Cohen's book, "Introduction to computer theory." There are plenty of examples of how to create a TG but nothing to determine how many can be created per language. I'm assuming I'm looking for finite amount of TG's? Thank You very much!</p>

http://mathoverflow.net/questions/71158/transition-graph-per-alphabet/71160#71160 Vijay D 2011-07-24T23:10:53Z 2011-07-24T23:10:53Z

<p>Adding a post because I lack the rep to comment. </p> <p>There is at least one graph per language (assuming a language is a finite or countably infinite set of finite-length words). There will in fact be infinitely many graphs per language. You need to restrict the question further to have interesting answers. Your first question is about the graphs over a given alphabet whereas the comment later is about graphs per language. There are markedly different. </p> <p><a href="http://en.wikipedia.org/wiki/Automata_theory" rel="nofollow">These</a> <a href="http://en.wikipedia.org/wiki/Computational_number_theory" rel="nofollow">pages</a> <a href="http://en.wikipedia.org/wiki/Graph_theory" rel="nofollow">may</a> help (the latter two based on your tags).</p>