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$. ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible