14
$\begingroup$

(Practice exam question in computational models)

Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.

Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and the first half of $w$ is unbalanced$\}$. Determine whether or not $L$ is context-free and prove your answer. You may do so by drawing an NPDA which recognizes $L$, using the closure properties of CFLs, or the relevant pumping lemma.

This question has been bugging me for a while; my gut tells me it isn't context-free since any PDA that recognizes it would have to check the balance of the string read thus far while simultaneously measuring its length and non-deterministically choosing an unbalanced point to validate as the middle of the word. I also haven't been able to express it as a union or concatenation of two CFLs or find a CFG which generates it.

On the other hand, I haven't been able to either find a word in the language that can't be pumped or prove that every word can be pumped.

Does anyone have any ideas on how to proceed?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Every word can be trivially pumped using pumping lemma for CFL. Just set v the first half of the word, and x the second half of the word. However this is not sufficient to claim it is CFL. $\endgroup$ – Marcelo Fornet Jun 20 '20 at 21:39
  • 1
    $\begingroup$ @MarceloFornet While your sentiment is shared, the length of $vx$ is greater than any fixed pumping length most of the time. A stronger claim would be that $L$ satisfies the pumping lemma. $\endgroup$ – John L. Jun 20 '20 at 22:34
  • $\begingroup$ @JohnL.Thanks for pointing out. Also was thinking the problem with the first half balanced. $\endgroup$ – Marcelo Fornet Jun 20 '20 at 23:07
  • 2
    $\begingroup$ Here is a possible approach. Try proving the following more general conjecture. Given a context-free language $H$, let $D=\{fb: f\in H, b\in\Sigma^*, |f|=|b|\}$. If $D$ is context-free, then $D$ is regular. $\endgroup$ – John L. Jun 22 '20 at 1:25
  • $\begingroup$ @JohnL. interesting idea, I’ll give it a shot. Tomorrow the TA for the course is holding a virtual office hour, too. I’ll ask her then and update here if she happens to have a solution. $\endgroup$ – Or Bairey-Sehayek Jun 22 '20 at 22:53
0
$\begingroup$

Perhaps it can be proved using Ogden's Lemma and its generalization by Bader and Moura, this is a rather informal sketch of the proof.

First restrict $L$ to strings of length $4n$ and apply to it the following homomorphism between $\Sigma = \{ 0,1 \}$ and $\Sigma' = \{ a, b, c\}$:

$h(11) \to a$
$h(00) \to b$
$h(01) \to c$
$h(10) \to c$

If $L$ is CF then also the new language $L'$ obtained is CF by closure properties.

Informally $L'$ contains an unbalanced number of $a$ and $b$ in the first half and the number/occurences of $c$ doesn't matter.

Further restrict $L'$ by intersecting it with the regular language $R = \{ a^* (c^* b^*)^* \}$; let $L'' = R \cap L'$

For example the string

$a a c b | cccc \in L''$ corresponds to $11\;11\;10\;00\; |\; 10\;10\;10\;10 \in L$ ($|$ is used to mark the half of the string for better readability)

$a b c c | cccc \notin L''$ corresponds to $11\;00\;10\;10\;|\;10\;10\;10\;10 \notin L$

Suppose that $L''$ is CF, and $p$ is its pumping length. Build $w \in L''$ concatenating these four parts:

  1. $(\;a^p\;)$ leading $a$'s

  2. $(\;c^j\;)$ a sequence of $c$s, we'll fix $j$ below

  3. $(\;c^{p} \;b\;)$ repeated $p + p!$

If $n$ is the constant of the Bader-Moura's condition, then we pick $j$ large enough to exclude all the symbols in part 1 and 3: $j \geq n^{p+(p+1)(p+p!)+1}$

  1. $(c^k)$ where $k$ is large enough to be pumped exluding all previous symbols: $k \geq n^{p + j + (p+1)(p+p!)+1}$

$w = a^{p} \; c^j \; (c^{p} \;b )^{p+p!} \; c^{k} $

Now we mark the first $a$ sequence as distinguished, the string $vx$ must contain $0 < q \leq p$ distinguished positions ($\#a_{vx} = q$) by Ogden's lemma; $vx$ can also contain one $b$ (not more than one because the $b$s are spaced with more than $p$ symbols $c$) and $0 \leq r < p$ symbols $c$ ($\#c_{vx} = r$).

  1. if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=0$, $\#c_{vx}=r$:

then we can pump $i = p! / q $ times and we obtain the same number of $a$s and $b$s; if after the pump some $b$s fall after the half of the string, we can pump the final $c^k$ independently from the rest of the string and we can "push" all $a$s and $b$s back in the first half (and $\#a_{w'} = \#b_{w'} = p + p!$), so the pumped string $w'$ is not in $L''$

  1. if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=1$, $\#c_{vx}=r$:

then each time we pump we increase the number of $a$s and $b$s, but we cannot guarantee that we reach the same number (e.g. in the case $\#a_{vx}=q=1\#b_{vx}$). But in this case the derivation tree "isolate" the $c^j$ part of the string from the final part $c^k$, so we can pump them independently.

We can pump $c^j$ as many time as needed to "push" $p!$ symbols $b$s to the second half of the string. Suppose that the pumping length of $c^j$ is $s$ (that must be even), the half of the string is shifted towards the $b$s by $s/2$. We have $s \leq p$ so after each pump at most one $b$ is "pushed" to the second half, because the "distance" between $b$s is $p$. So also in this case we get a string $w'$ not in $L''$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.