GATE CSE 2017 | Set 1 | Question: 43

Question

Consider the following grammar:

• stmt $\rightarrow$ if expr then expr else expr; stmt | $Ò$
• expr $\rightarrow$ term relop term | term
• term $\rightarrow$ id | number
• id $\rightarrow$ a | b | c
• number $\rightarrow [0-9]$ 

where relop is a relational operator $($e.g., $< , >,\ldots),$ $Ò$ refers to the empty statement, and if, then, else are terminals. 
Consider a program $P$ following the above grammar containing ten if terminals. The number of control flow paths in $P$ is________ . For example. the program 
if $e_1$ then $e_2$ else $e_3$ 
has $2$ control flow paths. $e_1 \rightarrow e_2$ and $e_1 \rightarrow e_3$. 

Comments

for 2 if statements there are 4 control flow graph 

thus, for 10 if statement there are 2^10 control flow graphs.

---

Possible silly mistake = doing 2*10 instead of 2^10.

---

no. of control flow paths $\rightarrow$ no. of $leaf$ nodes in $decision$ tree

$example:$ for 3 such statement's we can have 8 possibel control flow paths, no need of them being nested, it's just sequence of things happening one after another

why not $20?$

let's take an intiutive example 

$if$ (mood is okay) $then$ (study) $else$ (chillax);
$if$ (month is jan) $then$ (irrespective of mood study) $else$ (regret);

                            (Start Program)
                                  |
                                  |
                        Let's look at the first IF:    
                                  v
                       < Decision 1: Mood okay? >
                    /                            \
               (Yes/True)                        (No/False)
                  /                                \
                 v                                  v
       [ Action: Study ]                  [ Action: Chillax ]
                 |                                  |
                 |                                  |
         The first IF is done.            The first IF is done.
        Now everyone moves to            Now everyone moves to
          the second IF:                            |
                 v                                  v
        < Decision 2: Is it Jan? >        < Decision 2: Is it Jan? >
        /                \                /                \
   (Yes/True)        (No/False)      (Yes/True)        (No/False)
      /                    \            /                    \
     v                      v          v                      v
[LEAF 1]                 [LEAF 2]   [LEAF 3]                 [LEAF 4]
(Study anyway)           (Regret)   (Study anyway)            (Regret)

 

Answer 1

This question is picked from area of Counting in Combinatorics.

Given:
if $e_1$ then $e_2$ else $e_3$ has $2$ control flow paths $e_1 \rightarrow e_2$ and $e_1 \rightarrow e_3$.
(Meaning of "how many control flow" for if structure is clearly mentioned)

What is asked:
Number of control flow paths for $10$ if terminals?

Solution:
To get $10$ if's we need to use grammar to get,
         if <expr> then <expr> else <expr> ; stmt
         if <expr> then <expr> else <expr> ; if <expr> then <expr> else <expr> ; stmt
         ..............
         ..............
         ..............
         (keep doing it $10$ times to get $10$ if's)
Observe that there is a semi-colon after every if structure.

We know that every if structure has $2$ control flows as given in question. Hence,
        We have $2$ control flow choices for $1$st if terminal.
        We have $2$ control flow choices for $2$nd if terminal.
        ............
        ............
        ............
        We have $2$ control flow choices for $10$th if terminal.
        
By using multiplicative law of counting we get,
        Total choices as $2*2*2*2*2$......$10$ times $= 2^{10} = 1024$

Once again, one need not know "what control flow" is, but needs to know "how many control flows" are in if structure which is given in question.

Comments

@prs11Thanks for such great explanation..

---

How will i get to know these are nested loop at first glance i saw it one statement after another like this

 

if expr

  then expr

else

  expr;

if expr

  then expr

else

  expr;

.

.

.

And according to this i got, $2 + 2 +...+ 2 = 20$ (by using addition rule)

 

if expr

  then expr

else

  expr; if expr

              then expr

           else

               expr; if expr

                          then expr

                        else

                           expr; if expr       

                                      .

                                      .

                                      .

Now i can use product rule $2 * 2 * 2 * ..... * 2 = 2^{10}$

 

---

@RahulVerma3 It's not nested, the control flow is occurring exactly like the first part of your comment. But the number of control flows would be $2^{10}$ only. Every individual if-else block would have $ 2$ choices. The total possible control flows we'll get will be $2*2*2*...*2 (10$ times$)$

Answer 2

I will take a small example to make it clear.

Taking 2 if terminals

If expr then e1 else e2;

If expr then e3 else e4;

So there can be 4 control flow paths.

e1 e3

e1  e4

e2  e3

e2  e4

Now u can consider  10 if terminals.

The total control flow paths=2^10=1024.

Comments

@ Arjun  sir please tell me is my explanation of control flow path is correct or not?

---

I think you are totally correct in explaining because  here no correlation is there between any if then else. So each "if else then" have 2 options to take independent to other thus 2(1st) * 2(2nd).....so on it will be 1024 ways to select if else path ways for program P

---

🐐

Answer 3

A control flow path/control flow graph is a graphical representation of all paths that might be traversed through a program during its execution.

Now each $if$ statement has 2 outcomes ~ either true or false.

As per the grammar each if statement is independent of the other.

Consider 3 if statements

if e1 then e2 $(T)$ else e3 $(F)$;

if e4 then e5 $(T)$ else e6 $(F)$;

if e7 then e8 $(T)$ else e9 $(F)$;

Now following are the paths the program goes through during its execution :

$1. \ TTT$

$2. \ TTF$

$3. \ TFT$

$4. \ TFF$

$5. \ FTT$

$6. \ FTF$

$7. \ FFT$

$8. \ FFF$

So for $n = 3$ we have $2^{3} = 8$ control flow paths, hence for $n = 10$ we will have total $2^{10} = 1024$ control flow paths.

Comments

ya.....this one is correct explanation ; Initially i also thought it was 20. But they asked what are the total possible control paths we can have.

---

very nice explaination

---

Isnt the statements wrong, you are mapping t/f to then and else respectively.  So if you using nested loops , it should be if e1 then if e4 then e7 else e7  else  if e4 then e7 else e7 which gives the flow =2*2*2. Here each 2 count  is a mapping of T/F to the if expressions. Also , here each expression could be an expression or nested if itself so giving the10 ifs required for the question ie 2^10.

Answer 4

This might help.

 

Comments

This answer gave the best possible insight for this question. Thanks!

---

Best!

---

best answer and easiest to understand. thanks!

Answer 5

each if-else condition leads to two different paths, there are 10 if-else conditions one after the other, therefore totally 2¹⁰  = 1024 paths possible

Comments

I also got 20

---

Even I think it should be 20. Because nesting is not possible for the given grammar.

---

@Arjun Sir, @Uddipto pls correct me if I am wrong. 2^x is the total possible path. But for control path during the drerivation we have 2 choices for every if at that instant. Thus it should be 2*2*2* ... = 20

Answer 6

people considering 2.2....=2¹⁰  but tha happens when each 2 possiblity depends on the prevois possibility(counting rule---like topological sorting)

here for the Non-terminal expr no NESTING is done..

it will be like this..

for 3 if statement 

        every if statement is independent of previous one

so 20 should be the answer 

Comments

although its independent but if you see path for each if we have two choices so for similarly 10 if 2 choices each...and bdw if 1st if takes path from e1-e2 second if now has 2 choices similary remaining 8 have 2 choices each...so what you can say is that..no. of possible control flow paths is product of all 10 people choices that is 2^10

---

Key say 1024

---

But i also have confusion... In given grammer there is no assignment so  id/number can not have dependency of previous if else ...than according to the grammar only 20 possible