Let our alphabet be $\{x,(,),+\}$. A term is inductively defined as follows. $x$ is a term. If $s$ and $t$ are terms, so is $(s+t)$. Let $L$ denote the language of terms, and let $L'$ denote the same language after we delete all $x$'s and $+$'s from all the terms. This is in fact a language in the reduced alphabet $\{(,)\}$. The language $PAREN$ of balanced parentheses in this same alphabet is inductively defined by the rules: 1. The empty string is a member. 2. If $a$ and $b$ are members, so is $ab$. 3. If $a$ is a member, so is $(a)$. Let $(PAREN)$ refer to the language where every member is enclosed with one outermost parentheses. My conjecture is that the union of the language containing the empty string, along with $(PAREN)$ is equal to $L'$. Is this true? And if not, is it a subset of $L'$.
2026-04-04 15:17:18.1775315838
Question about a language in the alphabet {(,)}
66 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
$L'$ is a strict subset of $(PAREN) \cup \{ \text{empty word} \}$, because the parentheses in $L'$ only correspond to trees with at most two children while those in $(PAREN)$ correspond to any tree. For example, $(()()()()())$ is in $(PAREN)$ but not in $L'$.