Results 1 to 4 of 4

Math Help - countability of languages

  1. #1
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20

    countability of languages

    Let S = {0, 1}.

    (a) Let F1 be the set of all functions f : S ! IN.
    For example, the function f that has f(0) = 92873 and f(1) = 908 is one element of
    F1.
    Is F1 countable? Prove your answer is correct.

    (b) Let F2 be the set of all functions f : IN ! S.
    For example, the function f defined by f(n) = n mod 2 for all n 2 IN is one element
    of F2.
    Is F2 countable? Prove your answer is correct.

    p.s. ! means arrow to
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    What about this thread?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    Quote Originally Posted by emakarov View Post
    What about this thread?
    Honestly, I didn't understand the answer very well. If you sir can answer it, it would be great.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    (a) There is a one-to-one correspondence between the set of functions from S to \mathbb{N} and the set of pairs of natural numbers \mathbb{N}\times\mathbb{N}. Now, it is a standard result that there is a one-to-one correspondence between \mathbb{N}\times\mathbb{N} and \mathbb{N}: see Cantor pairing function, this proof, and this proof that the set of rational numbers is countable.

    (b) It is an equally standard result that this set is uncountable: see, for example, Cantor diagonal argument.
    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. context free languages
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2010, 06:11 PM
  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