ME test series

Question

Consider the following CFG, with S as start symbol:
S -> aA l CB
A -> BaA I e
B-> bB l Abc l e
C -> B
 

(HERE ‘e’ IS EPSILON OR NULL PRODUCTION)

1. FIRST(B)?

2. FOLLOW(C)?

Comments

First(B)---->>>>>>>>{b,$\epsilon$,a}

Follow(C)--------->>>{b,a,$}

Answer 1

	First	Follows
S	{a,b,epsilon}	{$}
A	{epsilon,b}	{$,b}
B	{epsilon,b}	{a,$}
C	{epsilon ,b}	{b,$}

 

Follow of C is what comes after c. So we can see from S -> CB that follow of C= first of B but as B contains epsilon also so follow of C also contains follow of S.

 

Comments

@Shubhanshu dont we just right epsilon instead of just placing it in all places where it can be placed and then checking it?please clarify and mention the source as I have studied that we do it in follow but in first we simply write epsilon 

---

No we can't just write $\epsilon$ but first, we substitute. And remember until unless the variable itself, not define epsilon or you got epsilon by replacement you will not going to write it in first set. Example make it clear:-

Suppose we have Grammar G:-

$A \rightarrow a/ BC \\ B \rightarrow b / \epsilon \\ C \rightarrow c / \epsilon$

Here we are getting $\epsilon$ in First set of (A) because we put $B = \epsilon \text{ and } C = \epsilon$ and not simply putting $\epsilon$ because B is defining $\epsilon$. Now Consider a variation of above grammar:-

$A \rightarrow a/ BCd \\ B \rightarrow b / \epsilon \\ C \rightarrow c / \epsilon$

Here $First(A)$ will not contain $\epsilon$ because even after replacement/substitution we are unable to get $\epsilon$.

BTW here $First(A) = \{a,b,c,d\}$.

---

@Shubhanshu I think that is because A does not have epsilon.. But for b we have { b, epsilon} and not {b,c,epsilon} pls clarify and can u pls mention any source so that I can further understand the things..

Answer 2

First (B) = Fi(bB) U Fi(Abc) U Fi(ϵ)   // here U is union and Fi is First

= {(b), Fi(A) U (ϵ)}  

// now Fi(A)= {Fi(BaA) U ϵ}  --------> put B= bB and ϵ , with ϵ you’ll get Fi(aA) = (a)

// So, Fi(A)= {a, b, ϵ}

             First (B) = {a, b, ϵ}

Follow(C)= First(B) = {a, b, ϵ}    

 in  S ->  CB   put B= ϵ then we will consider Fo(S) which is $

so,
Follow(C)=  {a, b, dollar symbol}

Comments

i was also getting same . there must have been mistake in given answer.

---

yes

---

ans this if you have time.

stack allocation can support pointers but can not deallocate storage at run time

(TRUE or FALSE)