10
Here is a simple direct proof that $L_{\text{diag}}$ is not empty.
Let $N$ be a Turing machine that does not accept any word. For example, a Turing machine that just loops forever. Suppose $N$ is encoded as the $j$-th machine. Then $L_{\text{diag}}$ contains the word $w_j$. Hence $L$ is not empty.
5
Usually that is a matter of taste. If I am nathematically motivated then I write $a^*$ like some single argument postfix operations in mathematics. If I keep close to applications, I would type $a*$ because typing superscripts in input for programs seems silly.
Same for $a^+$.
Be aware that in the context of regular expressions plus $+$ might have another ...
3
Since the diagonal language is not computable but the empty language is computable, that means that those languages are different.
2
Every rational language can be represented by (at least one) rational expression, and every rational expression represents a rational language. That means for any rational language, you can find the equivalent expression (though it might not always be a simple task). In fact, there are algorithms that convert any NFA into an equivalent rational expression ...
2
A regular grammar generates a regular language – the existence of a regular grammar for the language of palindromes would imply the language to be regular. However, it isn't, hence a regular grammar for it cannot exist.
2
Others have already suggested the simplest and most elegant ways to prove that the diagonal language is not empty.
Indeed, we can proceed by contradiction, and argue that if the diagonal language were empty, it would be recursive, but we know it is not. Or, more constructively, if we take any TM that recognizes the empty language, then it does not accept any ...
1
If $L$ is regular, then so is $L\{b\}^5$. You can conclude by studying $L\{b\}^5$ (which is a very classic language).
Also in your proof, you cannot guarantee that $j+k < p$, but $j+k < 5 + p$ is enough.
1
If you don't want to go through a DFA (which would definitely be the easiest systematic way of doing this), you can approach it by viewing the language as strings of 2, 1 or 0 zeros interleaved by ones:
$$(00 +0 + \epsilon)(1(00 + 0 + \epsilon))^*$$
1
Here is the answer.
Yes.
Yes.
Yes.
Yes.
Only top voted, non community-wiki answers of a minimum length are eligible