# Countable Set & Formal Grammar

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.

• Is $\Sigma$ really arbitrary or shouldn't we assume it is countable? – Hagen von Eitzen Aug 25 '14 at 14:41
• Dear @HagenvonEitzen, $\Sigma$ is arbitrary finite alphabet. – Mouna Mokhiab Aug 25 '14 at 15:44

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.

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