2 votes 2 votes Find the context-free grammar for the following language(n>=0 and m>=0) ? L={an bm : n<=m+3} Theory of Computation theory-of-computation grammar + – Ayush Upadhyaya asked Mar 19, 2017 Ayush Upadhyaya 4.9k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Ayush Upadhyaya commented Mar 19, 2017 reply Follow Share I had the following set of productions I divided the solution into 2 steps (1)For case n=m+3 S--->aaaaSb | epsilon (2)For Case n<m+3 S---> epsilon | aSb | aaSb | aaaSb Combining both cases 1 and 2 together we get S--->epsilon | aSb | aaSb | aaaSb | aaaaSb Please someone verify 0 votes 0 votes Akriti sood commented Mar 19, 2017 reply Follow Share but this will not produce single 'a'.,'aa','aaa' or epsilon as 'm' can also be 0 this will also not produce only streams of 'b s' as 'n' can be 0 even 0 votes 0 votes Ayush Upadhyaya commented Mar 19, 2017 reply Follow Share Yes, you are correct! I am trying to work out the solution but since I am a newbee to this topic, could you please suggest me some good resource so that I can get a decent grip on this topic? 0 votes 0 votes Ayush Upadhyaya commented Mar 19, 2017 reply Follow Share Also, if possible please help with the below question : https://gateoverflow.in/122090/peter-linz-exercise-5-1 0 votes 0 votes Please log in or register to add a comment.
Best answer 9 votes 9 votes $$\begin{align*} &S\rightarrow aSb \; |\; A \\ &A\rightarrow \epsilon \;|\; a \;|\; aa\;|\;aaa\;|\;B \\ &B\rightarrow bB\;|\;\epsilon \\ \end{align*}$$ dd answered Mar 19, 2017 selected Jun 30, 2018 by dd dd comment Share Follow See all 2 Comments See all 2 2 Comments reply Ayush Upadhyaya commented Mar 20, 2017 reply Follow Share Quite good approach. Infact the best I found anywhere. But Debashish I would like to know what is the base case using which you have considered the solution. I have understood the part when we can insert atmost 3 a's and it's when b is o(m=0). Please explain the second part where we are stopping S by inserting infinite b's . 0 votes 0 votes Mk Utkarsh commented Mar 20, 2018 reply Follow Share Ayush There is no restriction on generating b's but there is restriction on number of a's which is atmost 3 more than number of b's so when we want to stop generating strings then we can either generate ϵ|a|aa|aaa or b's(as many as we want) 0 votes 0 votes Please log in or register to add a comment.