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.

Mathematics,

I'm studying for a final that I have, and I need help with a problem.

Give a context-free grammar to generate the following language $L = \{ a^ib^jc^k \space|\space 0 \leq i \leq j \leq i + k \}$

What does $0 \leq i \leq j \leq i + k$ mean I should do in terms of creating the grammar? Does it mean the number of a's must be less than (or equal to) the number of b's, and the number of b's must be less than or equal to the number of a's and c's combined?

If so, here is my attempt.

$G = ({S, A, B, T, E},{a, b, c},{S, R})$

$S \rightarrow AB \\ A \rightarrow B \\ A \rightarrow aB \\ A \rightarrow a \\ B \rightarrow bB \\ B \rightarrow AB \\ B \rightarrow bbT \\ T \rightarrow cT \\ T \rightarrow cE \\ E \rightarrow \epsilon $

Is this correct? If so, can it be reduced to fewer rules?

Edit: I think I overthought it. Here's another try:

$G = ((S, T), (a, b, \epsilon), S, R)$

where $R$ contains the rules:

$S \rightarrow cSb \\ S \rightarrow T \\ T \rightarrow cTa \\ T \rightarrow \epsilon \\$

I believe this is correct, but it wouldn't hurt for a member to look at my answer.

Third attempt: $S \rightarrow AB \\ A \rightarrow aAb \\ B \rightarrow Bc \\ B \rightarrow bBc \\ A \rightarrow \epsilon \\ B \rightarrow \epsilon$

share|improve this question
    
Currently two of your exponents are i. I assume one of them should be a j. –  user18297 Dec 8 '12 at 5:03
    
@user18297 You're right, thank you. Fixed it. –  LearningPython Dec 8 '12 at 5:23
    
Your new grammar appears to construct the language $\{ c^{i+j} a^j b^i : i, j \geq 0 \}$. –  Arthur Fischer Dec 8 '12 at 5:36
    
In order to get the curly braces in $\{x:\varphi(x)\}$, use \{ and \}. –  Brian M. Scott Dec 8 '12 at 7:18
add comment

2 Answers

up vote 2 down vote accepted

Just as with computer programming, it’s a good idea to run some test derivations. Your first grammar permits the derivation of $bbcbbb$ via

$$S\to AB\to BB\to bbTB\to bbcTB\to bbcB\to bbcbB\to bbcbbbT\to bbcbbb\;,$$

but $bbcbbb\notin L$.

Your second grammar generates $\{c^ia^jb^k:i=j+k\}$, which wouldn’t be $L$ even if the $c$’s were on the right, because you have $i=j+k$ instead of $i\ge j+k$ and because you can have $j>k$. Part of the problem is that you started by generating the $b$’s and $c$’s; try starting with the $a$’s and $b$’s and using Arthur Fischer’s hint in his answer.

share|improve this answer
    
How about the third attempt? –  LearningPython Dec 12 '12 at 2:01
    
@LearningPython: That appears to work. You could also replace your third production by $B\to C$ and make $C$ do nothing but produce $c$’s. –  Brian M. Scott Dec 12 '12 at 2:06
    
Ok, thank you very much! –  LearningPython Dec 12 '12 at 2:08
    
@LearningPython: My pleasure! –  Brian M. Scott Dec 12 '12 at 2:08
add comment

Hint: Note that every string in your language can be expressed as $uv$ where $u \in \{ a^ib^i : i \geq 0 \}$ and $v \in \{ b^j c^k : 0 \leq j \leq k \}$ (and all such strings belong to your language).

share|improve this answer
    
Ok, how about the third attempt? –  LearningPython Dec 12 '12 at 1:55
    
@LearningPython: As Brian has already said, it looks perfect (and it is actually the same grammar I would have come up with). –  Arthur Fischer Dec 12 '12 at 4:49
add comment

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.