12
A TM does not have a register, but a register has a fixed capacity.
Any amount of fixed capacity storage can be emulated by multiplying your states: your new states become $ \langle q, v \rangle$ where $q$ is an old state and $v$ a value stored in the register.
So a "TM with a register" is not a TM, but trivially equivalent to a normal TM, and I ...
4
Yes a TM also has states. Formally, one can define TMs as $(Q, \Sigma, \Gamma, \square, \delta, q_0, \bar{q})$ with states $Q$, input alphabet $\Sigma$ not including the blank symbol $\square$, tape alphabet $\Gamma$, transition function $\delta$, initial state $q_0$ and terminal state $\bar{q}$. It might be differently defined but essentially it is all the ...
4
This is accomplished by the nondeterministic space hierarchy theory, given that CSL is the same as $\mathsf{NSPACE}(n)$.
3
When you look at the parser's process, you see the entire text to be parsed, and naturally make judgements based on that knowledge. But that's not the way the parser works. So your strategy makes it easy for you to parse utterances, but not easy for you to understand the parser.
Remember that the question is about a recursive descent parser with backtracking....
2
What about $\Sigma^*$ and $\Sigma^*\setminus\{11\}$?
1
In order to decide whether a context-free grammar generates the empty language or not, you can compute the set of productive nonterminals. A nonterminal $A$ is productive if there is a rule $A \to \alpha$ where all nonterminals in $\alpha$ are already known to be productive. The set of productive nonterminals can be computed iteratively using the definition. ...
1
In fact, you have identified a tip!
Let me make it more explicit. Suppose $L$ is context-free and $p>0$ is a pumping length for it as in the pumping lemma for context-free language. Try pumping up or down the word $a^pb^{p+1}c^p$ out of $L$.
(You can also pump up or down the word $a^pb^pc^{p+1}$ out of $L$.)
Only top voted, non community-wiki answers of a minimum length are eligible