2 votes 2 votes The context free grammar for the language: $L=\{a^n b^m \mid n \leq m + 3, n \geq 0, m \geq 0 \}$ is $S \rightarrow aaa \quad A; A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$ $S \rightarrow aaaA\mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$ $S \rightarrow aaaA \mid aa A \mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$ $S \rightarrow aaaA \mid aa \quad A \mid aA \mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$ Theory of Computation ugcnetcse-dec2013-paper2 theory-of-computation context-free-grammar + – go_editor asked Jul 26, 2016 recategorized Nov 11, 2017 by Sanjay Sharma go_editor 3.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes When m =0, n can be 0, 1,2,3 because n<=m+3 Such strings are λ, a, aa, aaa A. Cannot produce a,aa B. Cannot produce a,aa C.Cannot produce a D. Satisfies all conditions. hence D is the answer sh!va answered Jul 26, 2016 selected Sep 19, 2016 by Sankaranarayanan P.N sh!va comment Share Follow See 1 comment See all 1 1 comment reply Sanjay Sharma commented Jan 6, 2023 reply Follow Share This language can also generate strings like b,bb,bbb … which can’t be produced by any grammar of given options 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Ans (D) Ritwik answered Jun 18, 2017 edited Jun 18, 2017 by Ritwik Ritwik comment Share Follow See all 0 reply Please log in or register to add a comment.