3
votes
Accepted
Is the given language regular, CFL or in P
If a word is in your language, then it is of the form $w_1w_2$, where $|w_1| = |w_2|$ and $w_1$ contains a balanced string of length $100$, say $y$. Note that there are finitely many options for $y$. ...
1
vote
Determine the type of $L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$
The $|w|$ is even requirement can be checked by a finite state automaton, so that is not a real restriction. Comparing two numbers (the total length $|w|$ and the length of a consecutive sequence of $...
1
vote
Is there a TM that halts on all inputs but that property is not provable?
The halting of one TM can be encoded by constructing another TM and asking whether it halts. That is, given TM $T_1$ and input $I_0$, we can construct a TM $T_2$ with inputs indexed by the natural ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
computability × 1928turing-machines × 680
undecidability × 392
complexity-theory × 272
reductions × 216
formal-languages × 158
halting-problem × 152
semi-decidability × 125
computation-models × 108
automata × 70
decision-problem × 65
terminology × 61
context-free × 59
algorithms × 56
turing-completeness × 53
primitive-recursion × 53
finite-automata × 52
recursion × 51
regular-languages × 47
proof-techniques × 47
logic × 43
np-complete × 40
programming-languages × 37
formal-grammars × 36
closure-properties × 35