Results 1 to 2 of 2

Math Help - Formal Semantics of Programming Languages

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    1

    Formal Semantics of Programming Languages

    Hi everyone.
    I'm trying to be prepare for my exam. Our professor gave us a list of problem for our review. I don't get the question below. Can someone help me please

    Let X be a finite set. Can the set X x X be put in 1-1 correspondence with the set of all undirected graphs with vertex set X? Can the set X x X be put in 1-1 correspondence with the set of all directed graphs with vertex set X? For both cases, either show a correspondence or give a convincing argument that it cannot be accomplished.


    ---
    Thanks
    Mark
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2007
    From
    Melbourne
    Posts
    428
    This is probably too late to be helpful, but if you look at the cardinality of each set it is easy to see that there is no 1:1 correspondence
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automata Languages and DFA etc.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 20th 2011, 08:32 AM
  2. How many different languages?
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 22nd 2011, 05:56 AM
  3. Languages and FSM.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 5th 2011, 01:09 PM
  4. countability of languages
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 21st 2010, 11:18 AM
  5. countable languages..please help!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 17th 2010, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum