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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – Woot4Moo
    May 15, 2012 at 14:44
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ronny
    May 16, 2012 at 9:52
  • $\begingroup$ I see. I will make an attempt at this over the weekend and if anything comes of it I will make a post. $\endgroup$
    – Woot4Moo
    May 18, 2012 at 15:46
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jun 18, 2012 at 17:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ronny
    Jun 26, 2012 at 10:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.