Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$ 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).
Your summary of the proof of undecidability is not accurate.  Your specification of $\overline{A_{TM}}$ is not correct.

For a reasonable exposition of the proof, see https://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf particularly the beginning of Section 1 and Section 3.

The intuition is not easy to convey, as the proof is not entirely trivial.  But here is the core fact.  Let $v,w$ be two configurations of a Turing machine.  Write $n(v)$ to be the next configuration of the Turing machine after a single step of computation, if you start at configuration $v$.  Define the language

$$L = \{v \# w^R \mid n(v) \ne w\}.$$

Then the key fact is that $L$ is context-free.  This takes some proof; proving that is a key step in the proof.  However, that's the answer to your question: $L$ is context-free but not regular.  As a result, we can reduce the halting problem to $ALL_{CFG}$ but not to $ALL_{REX}$.

I have skipped many steps to give you an overview of the main idea.  You will need to read the full proof to fill in the details.  I suggest that you next read and understand the proof, with this perspective in mind, and then revisit what I've written here.  Hopefully that will help you understand why the proof holds for context-free languages but would fail for regular languages.