<p>For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given:
$$
L_{n,m} = \{ a^i | 2 \leq i \leq  m \} \setminus \{a^{2^i}|2 \leq i \leq  n-2\}  
$$
Find and prove a <em>minimal</em> context-free grammar according to the <em>number of rules</em> that generates $L_{n,m}$.</p>

<p>I think this cannot be done with a fewer number of rules as shown below:
$$
P = \{S \rightarrow a^{2^{i-1} + 1} A^{2^{i-1} - 2} | 2 \leq i \leq n-2 \} \cup \\ \{S \rightarrow a^{2^{n-2}+1}A^{m - (2^{n-2}+1)}, A \rightarrow a, A \rightarrow \epsilon\}
$$</p>

<p>Note: For the "complement" language
$$\{a^{2^i}|1 \leq i \leq  n\}$$
it’s known that a minimal context-free grammar needs exactly $n$ rules (one rule for each word $a^{2^i}$).</p>

<p>Any suggestions to prove or disprove my conjecture?</p>

CC BY-SA 3.0
2012-05-15T14:44:03.660Z
Unless I am missing something this does not look like a research level question.  Instead it looks like something out of my undergrad automata theory class.  I could be wrong though.
Woot4Moo
CC BY-SA 3.0
2012-05-16T09:52:50.520Z
This concrete language is important for me. It would help me to find the range of descriptional complexity (minimal number of rules of a context-free grammer that generates the language) a context-free languages can have under certain operations (like union, concatenation). Because we consider the minimal number of rules of context-free grammars this is not really part of theory of automata.
Ronny
CC BY-SA 3.0
2012-05-18T15:46:53.927Z
I see.  I will make an attempt at this over the weekend and if anything comes of it I will make a post.
Woot4Moo
CC BY-SA 3.0
2012-06-18T17:00:21.997Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
CC BY-SA 3.0
2012-06-18T17:03:50.260Z
As currently stated the question looks like a homework. If it is not please include the relevant context/background/motivation for the question in the post. You can find some suggestions on how to write a better question in the [FAQ].
Kaveh
CC BY-SA 3.0
2012-06-26T10:09:09.730Z
It’s no homework. It’s for a PhD thesis. This language could be from general interest for description complexity. Thus it’s relevant for theoretical computer science.
Ronny
CC BY-SA 3.0
2014-07-04T18:00:02.690Z
I don't know if it helps, but it's worth noting that your language is in fact regular. By Parikh's theorem, all context-free languages are letter-equivalent to regular languages, which in the unary case means that they are regular.
Joey Eremondi
<fl.formal-languages><optimization><context-free><context-free-languages>
Minimal context-free Grammar for a special one-letter Language
Ronny
# Minimal context-free Grammar for a special one-letter Language

(Asked by: username_0 on 2012-05-15)

For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given:
$$
L\_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\}
$$
Find and prove a *minimal* context-free grammar according to the *number of rules* that generates $L\_{n,m}$.

I think this cannot be done with a fewer number of rules as shown below:
$$
P = \{S \rightarrow a^{2^{i-1} + 1} A^{2^{i-1} - 2} | 2 \leq i \leq n-2 \} \cup \\ \{S \rightarrow a^{2^{n-2}+1}A^{m - (2^{n-2}+1)}, A \rightarrow a, A \rightarrow \epsilon\}
$$

Note: For the "complement" language
$$\{a^{2^i}|1 \leq i \leq n\}$$
it’s known that a minimal context-free grammar needs exactly $n$ rules (one rule for each word $a^{2^i}$).

Any suggestions to prove or disprove my conjecture?

**Tags:** fl.formal-languages, optimization, context-free, context-free-languages
> **Comments:**
> **username_1**: Unless I am missing something this does not look like a research level question.  Instead it looks like something out of my undergrad automata theory class.  I could be wrong though.  
> **username_0**: This concrete language is important for me. It would help me to find the range of descriptional complexity (minimal number of rules of a context-free grammer that generates the language) a context-free languages can have under certain operations (like union, concatenation). Because we consider the minimal number of rules of context-free grammars this is not really part of theory of automata.  
> **username_1**: I see.  I will make an attempt at this over the weekend and if anything comes of it I will make a post.  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  
> **username_2**: As currently stated the question looks like a homework. If it is not please include the relevant context/background/motivation for the question in the post. You can find some suggestions on how to write a better question in the [FAQ].  
> **username_0**: It’s no homework. It’s for a PhD thesis. This language could be from general interest for description complexity. Thus it’s relevant for theoretical computer science.  
> **username_3**: I don't know if it helps, but it's worth noting that your language is in fact regular. By Parikh's theorem, all context-free languages are letter-equivalent to regular languages, which in the unary case means that they are regular.  

---

## 0 answers

