recategorized by
3,593 views
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

  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$
recategorized by

2 Answers

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

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
2
go_editor asked Jul 26, 2016
2,871 views
Linux operating system usesAffinity schedulingFair Preemptive SchedulingHand ShakingHighest Penalty Ratio Next