Register

What is the number of terminal strings generated by given context-free grammar ?

• edited by
1,077 views
1 votes
1 votes

S→ A 0B
A→ BB|0
B →AA|1

What is the number of terminal strings of length 5 generated by the context-free grammar shown above?

  1. 4
  2. 5
  3. 6
  4. 7
• edited by
User Avatar

2 Answers

3 votes
3 votes
JUST GO WITH USUAL MANNER:

1. S-->A0B-->BB0AA-->11000.

2.S-->A0B-->BB0B-->AAB0B  OR   BAA0B

                            -->00101 OR   10001(TWO STRINGS)

3. S-->A0B-->A0AA-->A0ABB  OR A0BBA

                            --> 00011   OR 00110 (TWO STRINGS)

TOTAL 5 STRINGS
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
1 answer
2
ayushigupta asked Oct 17, 2015
2,186 views
What is the rank of the non-terminal B in the following context free grammar?
Consider the following CFG $S \to AB$ $A \to aBc \mid aB \mid a$ $B \to bDe \mid f \mid CD$ $C \to Dg \mid h$ $D \to g$ The rank of the non-terminal $B$ is __________
Consider the following CFG$S \to AB$$A \to aBc \mid aB \mid a$$B \to bDe \mid f \mid CD$$C \to Dg \mid h$$D \to g$The rank of the non-terminal $B$ is __________
User Avatar
0 votes
0 votes
1 answer
3
prasitamukherjee asked Jul 17, 2015
1,863 views
Regular or Context Free Grammar?
Consider the following statement: if (expression) statement else statement Which of the following describe the above statement? A). Regular grammar B). Context free grammar C). Both (A) and (B) D). None of these
Consider the following statement:if (expression) statement else statement Which of the following describe the above statement?A). Regular grammarB). Context free grammarC...
User Avatar
Link Copied!