All Questions
Tagged with context-sensitive computability
4 questions
4
votes
1
answer
76
views
Can you diagonalize a language out of CSL?
In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
-3
votes
2
answers
93
views
Is the language $\{ w \in \{ a, b \}^{*} | |w|_{a} + |w|_{b} = 2^{n} \}$ context sensitive? [closed]
Is the language $\{ w \in \{ a, b \}^{*} : |w|_{a} + |w|_{b} = 2^{n} \}$ context sensitive ?
1
vote
1
answer
620
views
context sensitive language finite or infinite
let L be a CSL. (my understanding/ memory/ expectation is) the problem
is L finite or infinite?
is undecidable.
where was this 1st proved/ published?
are there any cases in the literature of ...
- 11.1k
22
votes
3
answers
608
views
Machines for context-free languages which gain no extra power from nondeterminism
When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.
For the ...
- 18.3k