Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank you very much. Context-sensitive grammars interested me. I found this: 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.