1

I want to practice finding grammars for given languages. Unfortunately after solving some easy examples I found out that I completely don't know how to approach these more ambitious. For example when the task is to find grammar for $\left\{ a^i b^{i+2j}c^j: i,j\ge 0 \right\}$ it is very simple and after one minute I have a solution: $$S\rightarrow XY \\ X\rightarrow aXb \ | \ \varepsilon \\ Y\rightarrow bbYc \ | \ \varepsilon$$ However it has been 5 hours since I tried these examples:

a) $\left\{ a^{n^2} : n\ge 1 \right\}$

b) $\left\{ a^{2^n} : n\ge 1 \right\}$

c) $\left\{ a^n b^n c^n : n\ge 1 \right\}$

d) $\left\{ x\in \left\{ a,b,c \right\}^* : count_a(x) = count_b(x) = count_c(x) \right\}$

where $\left\{ a,b,c \right\}^*$ denotes set of all words consisting of letters $a,b,c$, and $count_a(x)$ is the number of occurrences $a$ in word $x$.

And I still can't manage to find grammars for above sets. Can anyone help?

xan
  • 2,053
  • 1
    For c), this is clearly not a context-free language (you can prove this with the pumping lemma for context-free languages), and i have my doubts about the other three as well. So this means you cant make up a grammar for it. Are you sure your question was to generate a context-free grammar for each part? – CarloV Feb 24 '13 at 14:30
  • Well, I'm new in this topic and so far I thought there are only context-free grammars. Then I apologize for misleading. The question is (translating exactly): "Find examples of grammars for:", so the solution indeed can be more complicated than I thought. But I'm still very curious how to solve these problems, and how big difference is between context-free and not context-free grammars. – xan Feb 24 '13 at 14:55
  • In that case try using context-sensitive grammars, i know these exist for b), c) and d). I think a) should also be possible in a context-sensitive grammar. – CarloV Feb 24 '13 at 16:15

1 Answers1

1

None of the four are context free, no wonder you didn't get grammars for them. By Parikh's theorem, for (a) and (b) the length of the strings must be a semilinear set, that is, representable by a finite number of expressions of the form $\alpha k + \beta$, and that is impossible as the distance from $n^2$ to $(n + 1)^2$, and from $2^n$ to $2^{n + 1}$, grows without limit.

For (c), by the pumping lemma for context free languages, assume for the sake of contradiction that the language is context free, and let $p$ be the constant of the lemma. Then $s = a^p b^p c^p$ is longer than $p$, so it can be written $s = u v x y z$ with $v$, $y$ not both empty such that $u v^k x y^k z$ is part of the language for all $k \ge 0$. But by repeating $v$ and $y$ at most two of $a$, $b$, $c$ can grow while maintaining the general form of $a$s followed by $b$s and then $c$s, and the equality isn't maintained.

For (d), the context free languages are closed with respect to intersection with regular languages (see here). But the intersection of this language with $a^* b^* c^*$ is precisely the non-context free language of (c), so it can't be context free.

vonbrand
  • 27,812
  • Thank you very much. Context-sensitive grammars interested me. I found this: http://en.wikipedia.org/wiki/Context-sensitive_grammar#Examples I was wondering if you can explain to me why in this link grammar for c) is OK? First question: why can't we just use simply $CB\rightarrow BC$ and we need to do this in few steps using nonterminal $H$? Second: is order of rules relevant? Because when we use this grammar like that: $S\rightarrow aSBC \rightarrow aaBCBC \rightarrow aabCBC \rightarrow aabcBC$ then we are in dead end. I suppose I don't understand something here. – xan Feb 24 '13 at 17:20
  • @xan, better formulate that as a separate question. – vonbrand Feb 24 '13 at 17:22