I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ refer to the language that a given CFG generates $\Sigma^*$, and let $ALL_{REX}$ refer to the language that a given regular expression generates $\Sigma^*$ (and since for each regular expression there is a regular grammar, we can also say that the equivalent regular grammar generates $\Sigma^*$).
From what I got, we have:
$ALL_{CFG}$ is not decidable, it is also not Turing-recognizable. Let $\overline{A_{TM}}$ refer to the language that a TM $M$ does not accept input word $w$. We can reduce $\overline{A_{TM}}$ to $ALL_{CFG}$ in polynomial time using computation histories. The reduction constructs a CFG which generates all possible words where: 1) the first characters do not match $w$, 2) the last characters do not match accepting configurations, and 3) characters do not match valid transitions of $M$'s configurations. Thus, $A_{TM}$ does not accept $w$ iff the CFG generates $\Sigma^*$ (i.e. there are no accepting computation histories). Since the reduction maps $\overline{A_{TM}}$ to $ALL_{CFG}$, and $\overline{A_{TM}}$ is not Turing-recognizable, $ALL_{CFG}$ is not Turing-recognizable.
$ALL_{REX}$ is decidable since it is decidable if a finite automaton accepts $\Sigma^*$. However, the acceptance problem for any regular language $R$ can be polynomially reduced to the language $ALL_{REX} - f(R_M)$, where $R_M$ is a TM that decides $R$, and $f(R_M)$ is a similar reduction of computation histories as outlined above. In more detail, $f(R_M)$ is the regular grammar that generates all possible words where 1) the first characters do not match $w$, 2) the last characters do not match rejecting configurations, and 3) characters do not match valid transitions of $R_M$'s configurations. The decider for $ALL_{REX} - f(R_M)$ checks if it is empty (which means that $f(R_M)$ is equal to $\Sigma^*$). If empty, then there are no rejecting computation histories and $w \in R$. (In Sipser, he used something like this to show EXPSPACE-completeness for $ALL_{REX} - f(R_M)$)
I would like to ask:
From above, both regular grammars and CFG could generate computation histories of a TM, and both could generate $\Sigma^*$. But what is it with the fundamental power of the CFG's grammar that makes it valid to reduce $\overline{A_{TM}}$ to $ALL_{CFG}$, but it is not possible for $\overline{A_{TM}}$ to be reduced to $ALL_{REX} - f(A_{TM})$ ? I know that we cannot reduce $\overline{A_{TM}}$ to $ALL_{REX} - f(A_{TM})$ since $ALL_{REX} - f(A_{TM})$ is decidable, while $\overline{A_{TM}}$ is not Turing-recognizable... But I would like to understand this in terms of the difference in generating power between CFG's and regular grammars via their rules.
For instance, from what I read, CFG's permit the rules $A \rightarrow BC$, where $B$ and $C$ are strings of variables and terminals. On the other hand, regular grammars only permit rules in the form of $A \rightarrow aB$, where $a$ is a terminal. I would like to ask: why does incorporating rules of the form $A \rightarrow BC$ to a grammar, give it enough generating power such that it is already valid to reduce $\overline{A_{TM}}$ to the grammar (i.e. to the CFG).
