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$. ...
- 270k
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 $...
- 27.6k
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 ...
- 710
Only top scored, non community-wiki answers of a minimum length are eligible