1
$\begingroup$

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

I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary alphabet. every one would please help me and add some hints for each one, or if I'm wrong correct me !! thanks to all.

1) Each arbitrary Language on $\Sigma$ is Countable.

2) the set of all language from $\Sigma$ is Countable.

3) for Each arbitrary Language on $\Sigma$ we have a generative formal grammar.

4) Each arbitrary Language on $\Sigma$ that generated by formal grammar, is recursive.

$\endgroup$
  • 1
    $\begingroup$ Is $\Sigma$ really arbitrary or shouldn't we assume it is countable? $\endgroup$ – Hagen von Eitzen Aug 25 '14 at 14:41
  • 1
    $\begingroup$ Dear @HagenvonEitzen, $\Sigma$ is arbitrary finite alphabet. $\endgroup$ – Mouna Mokhiab Aug 25 '14 at 15:44
1
$\begingroup$
  1. If $\Sigma$ is any finite alphabet (or even countably infinite), then $\Sigma^*$ is countable, hence so is any language on $\Sigma$

  2. Let $a\in\Sigma$ be an arbitrary letter. Then for any subset $A\subseteq\mathbb N$, we have the language $\{\,a^n\mid n\in A\,\}$. As there are uncoutably many subsets of $\mathbb N$, there are uncountably many languages.

  3. Grammars are allowed to have only finitely many rules and metavariabables, hence there are only countably many grammars - less than there are languages.

  4. Indeed, one can transform a grammar into a Turing machine that shows recursiveness.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Dear Hagen, you means 1, 3 and 4 is True ? $\endgroup$ – Mouna Mokhiab Aug 25 '14 at 17:50
  • $\begingroup$ I try lots of note's today. I think just 1 is true... $\endgroup$ – Mouna Mokhiab Aug 25 '14 at 18:39
  • $\begingroup$ Dear @Hagen, please let me know about my comment !! $\endgroup$ – Mouna Mokhiab Aug 26 '14 at 12:31
  • 1
    $\begingroup$ I suggest that 1 and 4 are true. $\endgroup$ – Hagen von Eitzen Aug 26 '14 at 19:13
  • $\begingroup$ I think 4 is false? there exist a recursively enumerable language that is not recursive. $\endgroup$ – Mouna Mokhiab Aug 26 '14 at 19:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.