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 '12 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 '12 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 '12 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 '12 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 '12 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.