GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
77 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 (77.7k points)   | 77 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 (27k points)  
selected by
0 votes

Ans (D)

 

 

answered ago by (217 points)  
edited ago by


Top Users Jun 2017
  1. Bikram

    3694 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1372 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1114 Points

  8. Arjun

    930 Points

  9. srestha

    922 Points

  10. Debashish Deka

    896 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1950 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,353 questions
30,061 answers
67,357 comments
28,378 users