# Is the given language regular, CFL or in P

someone sent me a question lately and I wasn't able to solve it so I'm asking for help.

Question: Given the language $$L=\{w\in\{0,1\}^*:|w| \text{ is even and the first half of it has a balanced string of length } 100\}$$

Balanced: A string $$w\in\{0,1\}^*$$ is said to balanced if it has the same number of $$0$$'s and $$1$$'s in it.

My suggestion:

1. Since the number of balanced strings of length 100 is finite build a DFA for each balanced string of length 100 that accepts it.
2. Build a new NFA which has an initial state that has $$\epsilon$$ edge to each one of the initial states of the DFA's in section 1. Moreover, the initial state has a loop on it that accepts $$0$$'s and $$1$$'s.
3. From each accepting state of the DFA's from section 1 add $$\epsilon$$ edge to a new accepting state of the NFA from section 2. The new accepting state also has a loop on it that accepts $$0$$'s and $$1$$'s.
4. Remove all the accepting states of the NFA except for the accepting state of section 3. The same thing for the initial state, remove all the initial states of the NFA except for the one of section 2.

So this suggestion works perfectly as I assume but it's problem that it can accept balanced words of length 100 beyond the first half of $$w$$. What can I do in that case?

Note: The language could be not regular but I assume that it's regular so I'm trying to build NFA for it, please correct me if I'm wrong.

• When you say "first half" do you just mean that it has to have a prefix of length 100 or that the full length has to be exactly 200?
– Jake
Jun 8, 2022 at 20:10
• If you consider $w$ as a Java string then the balanced string must be in $w[0]$ to $w[|w|/2]$. Jun 8, 2022 at 20:35
• All context-free languages are in P. Jun 8, 2022 at 20:50
• @MohamadS. I'm asking about you're phrasing saying "the first half must be balanced", it isn't clear if you mean that w = ab where a is a balanced string and b is of the same length or if b is allowed to be any string at all as long as w is of even length.
– Jake
Jun 8, 2022 at 21:03
• Consider $w=01010000$ and we request a balanced word of length 4 in the first half so there is 1 like this which is $0101$. However, consider $w=01110100$, notice that there is $1010$ but it's not found in the first half since the first half ends at the 4th letter. Jun 9, 2022 at 8:10

## 1 Answer

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$$. We can write $$w_1 = xyz$$. Now let's break $$w_2$$ into $$z'y'x'$$, where $$|x| = |x'|$$, $$|y| = |y'| = 100$$ and $$|z| = |z'|$$. If $$|x| = i$$ and $$|y| = j$$, then $$w$$ belongs to $$\Sigma^i y \Sigma^{2j + 100} \Sigma^i.$$ You take it from here.

To show that your language isn't regular, consider words of the form $$0^i 1^{50} 0^j$$.

• Well, thanks a lot I really struggled with this question. Jun 8, 2022 at 20:59