Language with middle third removed

2.4k Views Asked by At

Originating from Sipser's book:

Let $A$ be any language, define $A_{{1\over3}-{1\over3}}$ be the subset of strings of $A$ whose middle third is removed.

The solution I came across makes the following claim, which I cannot justify: Let $A=\{0^*\#1^*\}$ then $A_{{1\over3}-{1\over3}}\cap\{0^*1^*\} = \{0^n1^n\mid n\geq 0\}$. For example consider the string $w=0000\#1$, removing the middle third will yield $00\#1$ and whose intersection with $\{0^*1^*\}$ is $\emptyset$ which not of the form $\{0^n1^n\mid n\geq 0\}$. Is there something I am not seeing? Thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

In the question, $A_{{1\over3}-{1\over3}}\cap\{0^*1^*\}$ is an intersection of two languages: $00\#1$ is in the language $A_{{1\over3}-{1\over3}}$ but not in the language $\{0^*1^*\}$, so it is not in the intersection of the two languages. You shouldn't be thinking of intersecting a (single) string like $00\#1$ with a language (i.e., set of strings) like $\{0^*1^*\}$.

A string $s$ belongs to $A_{{1\over3}-{1\over3}}$ iff you can form it from a string $t$ of the form $0^p\#1^q$ by deleting the middle third from $t$. Then $s$ will be in $\{0^*1^*\}$ iff the $\#$ was in the middle third of $t$. The question is asking you to show that if that happens, then $s$ contains an equal number of $0$s and $1$s.