GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
94 views

The context free grammar for the language:

$L=\{a^n b^m \mid n \leq m + 3, n \geq 0, m \geq 0 \}$ is

  1. $S \rightarrow aaa \quad A; A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$
  2. $S \rightarrow aaaA\mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$
  3. $S \rightarrow aaaA \mid aa A \mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$
  4. $S \rightarrow aaaA \mid aa \quad A \mid aA \mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$
asked in Others by Veteran (79.2k points)   | 94 views

2 Answers

+3 votes
Best answer

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

answered by Veteran (27.8k points)  
selected by
0 votes

Ans (D)

 

 

answered by (217 points)  
edited by


Top Users Aug 2017
  1. Bikram

    5174 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3504 Points

  4. manu00x

    3492 Points

  5. rahul sharma 5

    3188 Points

  6. makhdoom ghaya

    2700 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2090 Points

  10. pawan kumarln

    1874 Points


25,065 questions
32,220 answers
75,083 comments
30,231 users