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.

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?

My attempt:

$G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of: $$ S\to AbBC $$ $$A \to aAb|\lambda$$ $$ B \to bB|\lambda $$ $$ C \to bCa|\lambda$$

Is this correct?

share|improve this question
    
This has been flagged as off-topic. Is there a better place for it? –  robjohn Apr 24 '13 at 15:54
    
@robjohn I think cs.stackexchange.com would be a much better fit. –  haunted85 Apr 24 '13 at 15:59
    
@haunted85 The same user asked (almost) the same question on Computer Science earlier this day and deleted it again. Not clear whether the reason was self-vandalism, sulkiness or something else entirely. –  Raphael Apr 24 '13 at 17:27
1  
@haunted85: We routinely answer such questions. –  Brian M. Scott Apr 24 '13 at 21:05
3  
This is a special case of this recent question; the accepted answer there, combined with Arthur Fischer’s answer, should help. –  Brian M. Scott Apr 24 '13 at 21:06
show 2 more comments

1 Answer

up vote 2 down vote accepted

The strings your grammar generate are of the form $\mathtt{a}^i \mathtt{b}^{j} \mathtt{a}^k \mathtt{b}^k$ (or $\mathtt{0}^i \mathtt{1}^{j} \mathtt{0}^k \mathtt{1}^k$ with notational changes) where $j > i$. (You're use of the non-terminal $A$ in two spots in the starting rule made you go awry as the order of the $\mathtt{a}$s and $\mathtt{b}$s (or $\mathtt{0}$s and $\mathtt{1}$s) matters.)

Don't be afraid to use more non-terminal symbols! (well, one more.)

share|improve this answer
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.