Register

Test by Bikram | Mock GATE | Test 2 | Question: 38

• retagged by
791 views
1 votes
1 votes
  • $S\rightarrow A0 B$
  • $A\rightarrow BB \mid 0$
  • $B\rightarrow AA \mid 1$


 The number of terminal strings of length $5$ generated by the context-free grammar shown above is _______.

• retagged by
User Avatar

5 Answers

Best answer
5 votes
5 votes
5 strings

1. s-> A0B -> BB0B -> BB0AA-> 1B0AA ->110AA ->1100A ->11000

2. s-> A0B -> BB0B -> 1B0B -> 1AA0B -> 10A0B -> 1000B ->10001

3. S-> A0B -> BB0B -> BBB0B ->1BB0B -> 11B0B -> 1110B ->11101

4.S-> A0B ->00B -> 00BB -> 00BBB -> 001BB ->0011B-> 00111

5.S-> A0B -> 00B -> 00BB-> 001B -> 001BB -> 0011B -> 00111

I did left most derivation..I tried to bold but I am unable to do.Hope you can Understand
• selected by
User Avatar
2 votes
2 votes

    S --> A0 B

    A--> BB | 0

    B ---> AA |1

We can actually answer this question smartly :D

1)Remove B above.

    S --> A0AA   |  A01

    A--> AAAA | AA1 |1AA | 11 | 0

2) S--> A0AA

Try replacing A , Since we need a length 5 string only way we can replace A is

One of the A's replace by 11 and others by 0. ------> 3 ways ( 11000,00110,00011)

3)S-->A01

Try replacing A , Since we need a length 5 string only way we can replace A is by AA1 or 1AA

S-> AA101  |  1AA01 ; Only way to replace A is by A->0

----> 2 ways (00101,10001)

Total=3+2 = 5 strings

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

5 votes
5 votes
1 answer
1
Bikram asked Jan 24, 2017
513 views
Test by Bikram | Mock GATE | Test 2 | Question: 14
Consider the following code snippet. void first(int p, int t) { p += t; t += p; } main() { int p = 4; first(p , p); } What is the final value of $p$ in both call by value and call by reference respectively ? $4$ and $12$ $5$ and $12$ $12$ and $16$ $4$ and $16$
Consider the following code snippet.void first(int p, int t) { p += t; t += p; } main() { int p = 4; first(p , p); }What is the final value of $p$ in both call by value a...
User Avatar
5 votes
5 votes
1 answer
2
Bikram asked Jan 24, 2017
977 views
Test by Bikram | Mock GATE | Test 2 | Question: 46
The number of possible Deterministic Finite Automation with two states $q_0$ and $q_1$, where $q_0$ is always the initial state over the alphabet $\left \{ a,b \right \}$ which accept empty language is : ____________.
The number of possible Deterministic Finite Automation with two states $q_0$ and $q_1$, where $q_0$ is always the initial state over the alphabet $\left \{ a,b \right \}$...
User Avatar
4 votes
4 votes
2 answers
3
Bikram asked Jan 24, 2017
491 views
Test by Bikram | Mock GATE | Test 2 | Question: 64
The value of the expression $1 - 6 + 2 - 7 + 3 - 8 +$……… to $100$ terms is __________.
The value of the expression $1 - 6 + 2 - 7 + 3 - 8 +$……… to $100$ terms is __________.
User Avatar
Link Copied!