We know set A is countable if A is finite or in a one-to-one mapping to natural numbers.

Suppose $\Sigma$ be an arbitrary finite alphabet.

I summarize my inference:

a) Each arbitrary Language on $\Sigma$ is Countable. (I think this is True)

b) the set of all language from $\Sigma$ is Countable.(I think this is False)

c) for Each arbitrary Language on $\Sigma$ we have a generative formal grammar. (I think this is False)

d) Each arbitrary Language on $\Sigma$ that can be generated by formal grammar, is recursive. (I think this is True)

anyone could help me, and maybe correct me?

  • $\begingroup$ Are you assuming your alphabet is countable? $\endgroup$ – Lee Mosher Oct 4 '14 at 14:09
  • $\begingroup$ @LeeMosher Aren't alphabets always countable? $\endgroup$ – TheWaveLad Oct 4 '14 at 14:10
  • $\begingroup$ Dear @LeeMosher, i edit it. sorry. $\endgroup$ – Mina Soli Oct 4 '14 at 14:14
  • $\begingroup$ Dear @vaultboy, I edit it. $\endgroup$ – Mina Soli Oct 4 '14 at 14:21
  • 1
    $\begingroup$ @Mina Soli: could you add your reasoning for why you think each one is true or false? Then we can comment on that. Otherwise, there isn't much we can say. "I think this is true" is not a mathematical argument on its own. $\endgroup$ – Carl Mummert Oct 4 '14 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.