<p><strong>Lemma 1.</strong> <em>Consider</em> <span class="math-container">$L = (ab)^* + (ba)^*$</span>:</p>
<ol>
<li><em>There exists CFG with two variables which generates</em> <span class="math-container">$L$</span></li>
<li><em>There exist no CFG with one variable which generates</em> <span class="math-container">$L$</span></li>
</ol>
<p>For proving (1) we may just consider the following CFG <span class="math-container">$$ S \rightarrow bAa \mid A , \, A \rightarrow abA \mid \varepsilon$$</span>
The second proposition is a bit more tricky. Suppose that there exists CFG <span class="math-container">$G = (\{S\}, \{a, b\}, P, S)$</span> such that <span class="math-container">$L = L(G)$</span>. Every production is <span class="math-container">$S \rightarrow \alpha$</span> for some <span class="math-container">$\alpha \in \{a, b, S\}^*$</span>. Say, <span class="math-container">$\alpha = w_1 S w_2 S \ldots w_k S w_{k+1}$</span>. Then <span class="math-container">$$u_1, \ldots u_k \in L \Rightarrow w_1 u_1 w_2 u_2 \ldots w_k u_k w_{k+1} \in L,$$</span> because as <span class="math-container">$L$</span> is generated by <span class="math-container">$G$</span>, one can derive this word by using <span class="math-container">$S \rightarrow w_1 S w_2 S \ldots w_k S w_{k+1}$</span> and then deriving every <span class="math-container">$u_i$</span> from <span class="math-container">$S$</span>'s. By using that we can prove that in right-hand side of every production <span class="math-container">$S$</span> can't be followed immediately by any symbol:</p>
<ul>
<li>if <span class="math-container">$S$</span> is followed by <span class="math-container">$a$</span>, we have subword <span class="math-container">$Sa$</span> in <span class="math-container">$\alpha$</span>, then we can derive <span class="math-container">$ba$</span> from <span class="math-container">$S$</span>, thus we can derive the word which contains two <span class="math-container">$a$</span>'s in the row, which obviously doesn't lie in <span class="math-container">$L$</span>;</li>
<li>if <span class="math-container">$S$</span> is followed by <span class="math-container">$b$</span>, having subsword <span class="math-container">$Sb$</span> of <span class="math-container">$\alpha$</span> we can derive <span class="math-container">$ab$</span> from <span class="math-container">$S$</span> and thus obtain the word which contains two <span class="math-container">$b$</span>'s in the row;</li>
<li>if we have subword <span class="math-container">$SS$</span> of <span class="math-container">$\alpha$</span>, we can derive <span class="math-container">$ab$</span> from the first <span class="math-container">$S$</span> and <span class="math-container">$ba$</span> from the second.</li>
</ul>
<p>Also <span class="math-container">$S$</span> can't follow neither letter nor <span class="math-container">$S$</span> in right-hand side of every production for the same reason. So <span class="math-container">$G$</span> can only have productions of sort <span class="math-container">$S \rightarrow S$</span> and <span class="math-container">$S \rightarrow w$</span> for <span class="math-container">$w \in L$</span>. Thus <span class="math-container">$L(G)$</span> is finite, which is contradiction. <span class="math-container">$\Box$</span></p>
<p>I'd also like to suggest the following</p>
<p><strong>Lemma 2.</strong> <em>Let <span class="math-container">$w_1, \ldots w_n$</span> be some words. The language</em> <span class="math-container">$w_1^* + \ldots + w_n^*$</span> <em>is generated by CFG with one variable iff words</em> <span class="math-container">$w_1, \ldots w_n$</span> <em>commute pairwise, i. e.</em> <span class="math-container">$w_i w_j = w_j w_i$</span> <em>for every</em> <span class="math-container">$i,j$</span>.</p>

CC BY-SA 4.0
2020-12-30T20:03:31.287Z
2020-12-30T20:03:31.287Z
DG_
<p>Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below.</p>
<p>I am aware of an <a href="https://www.sciencedirect.com/science/article/pii/S0019995871905195" rel="nofollow noreferrer">old Grushka's article</a> and a <a href="https://dl.acm.org/doi/abs/10.5555/1377804.1377809" rel="nofollow noreferrer">more recent paper by Dassow and Stiebe</a>. I've also found <a href="https://repositum.tuwien.at/bitstream/20.500.12708/15037/2/Grammatical%20Complexity%20of%20Finite%20Languages.pdf" rel="nofollow noreferrer">Wolfsteiner's thesis</a>.</p>
<p>What is the state of art of the study of grammar complexity? Could you explain simply the connection between grammar complexity and formal proof theory?</p>

CC BY-SA 4.0
2021-01-03T20:38:36.533Z
What do you mean by formal proof theory here?
Martin Berger
CC BY-SA 4.0
2021-01-16T20:15:50.230Z
@MartinBerger Sorry for being this late; I mean that according to [Hetzl](https://link.springer.com/chapter/10.1007%2F978-3-642-28717-6_19) proofs could be compressed via grammar-based compression of a finite tree language.
DG_
<fl.formal-languages><regular-language><context-free><descriptive-complexity>
Nonterminal descriptional complexity of regular languages
DG_
# Nonterminal descriptional complexity of regular languages

(Asked by: username_0 on 2020-12-30)

Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below.

I am aware of an [old Grushka's article](https://www.sciencedirect.com/science/article/pii/S0019995871905195) and a [more recent paper by Dassow and Stiebe](https://dl.acm.org/doi/abs/10.5555/1377804.1377809). I've also found [Wolfsteiner's thesis](https://repositum.tuwien.at/bitstream/20.500.12708/15037/2/Grammatical%20Complexity%20of%20Finite%20Languages.pdf).

What is the state of art of the study of grammar complexity? Could you explain simply the connection between grammar complexity and formal proof theory?

**Tags:** fl.formal-languages, regular-language, context-free, descriptive-complexity
> **Comments:**
> **username_1**: What do you mean by formal proof theory here?  
> **username_0**: @MartinBerger Sorry for being this late; I mean that according to [Hetzl](https://link.springer.com/chapter/10.1007%2F978-3-642-28717-6_19) proofs could be compressed via grammar-based compression of a finite tree language.  

---

## 1 answers

### Answer by username_0 on 2020-12-30. Score: 2

**Lemma 1.** *Consider* $L = (ab)^\* + (ba)^\*$:

1. *There exists CFG with two variables which generates* $L$
2. *There exist no CFG with one variable which generates* $L$

For proving (1) we may just consider the following CFG $$ S \rightarrow bAa \mid A , \, A \rightarrow abA \mid \varepsilon$$
The second proposition is a bit more tricky. Suppose that there exists CFG $G = (\{S\}, \{a, b\}, P, S)$ such that $L = L(G)$. Every production is $S \rightarrow \alpha$ for some $\alpha \in \{a, b, S\}^\*$. Say, $\alpha = w\_1 S w\_2 S \ldots w\_k S w\_{k+1}$. Then $$u\_1, \ldots u\_k \in L \Rightarrow w\_1 u\_1 w\_2 u\_2 \ldots w\_k u\_k w\_{k+1} \in L,$$ because as $L$ is generated by $G$, one can derive this word by using $S \rightarrow w\_1 S w\_2 S \ldots w\_k S w\_{k+1}$ and then deriving every $u\_i$ from $S$'s. By using that we can prove that in right-hand side of every production $S$ can't be followed immediately by any symbol:

* if $S$ is followed by $a$, we have subword $Sa$ in $\alpha$, then we can derive $ba$ from $S$, thus we can derive the word which contains two $a$'s in the row, which obviously doesn't lie in $L$;
* if $S$ is followed by $b$, having subsword $Sb$ of $\alpha$ we can derive $ab$ from $S$ and thus obtain the word which contains two $b$'s in the row;
* if we have subword $SS$ of $\alpha$, we can derive $ab$ from the first $S$ and $ba$ from the second.

Also $S$ can't follow neither letter nor $S$ in right-hand side of every production for the same reason. So $G$ can only have productions of sort $S \rightarrow S$ and $S \rightarrow w$ for $w \in L$. Thus $L(G)$ is finite, which is contradiction. $\Box$

I'd also like to suggest the following

**Lemma 2.** *Let $w\_1, \ldots w\_n$ be some words. The language* $w\_1^\* + \ldots + w\_n^\*$ *is generated by CFG with one variable iff words* $w\_1, \ldots w\_n$ *commute pairwise, i. e.* $w\_i w\_j = w\_j w\_i$ *for every* $i,j$.


---

