GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
140 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 (92.6k points) 975 2337 3116 | 140 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 (30.2k points) 108 374 692
selected by
0 votes

Ans (D)

 

 

answered by (365 points) 1 3 7
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23438 Points

  2. Bikram

    17108 Points

  3. Habibkhan

    8354 Points

  4. srestha

    6314 Points

  5. Debashish Deka

    5458 Points

  6. jothee

    5008 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4390 Points

  9. sushmita

    3996 Points

  10. Rishi yadav

    3840 Points


Recent Badges

Popular Question sunil sarode
Verified Human nandisrinivas
Nice Question shraddha priya
Popular Question just_bhavana
Famous Question rahul sharma 5
Popular Question Jithin Jayan
Great Answer Sankaranarayanan P.N
Good Question jothee
Great Answer Sankaranarayanan P.N
Famous Question pC
27,346 questions
35,200 answers
84,230 comments
33,327 users