The halting problem is described as the impossibility to know if a program $($based on any

programming language$)$ will halt or not after it starts running.

How would you simulate or semi$-$simulate the halting problem? If a simulation is possible,

provide a graph or a flow chart. Explain your reasoning.

If a simulation is not possible, explain your reasoning. $(10$ points$)$

Convert the following CFG into Chomsky Normal Form $($CNF$)$:

$S$AbA

$AAa|$

$(30$ points$)$