The Gateway to Computer Science Excellence

+38 votes

Consider the following grammar:

- stmt $\rightarrow$
**if**expr**then**expr**else**expr; stmt | $0$ - 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.. $<$ . $>$ ...). $0$ 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$.

+59 votes

Best answer

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.

+3

**The Number of Control Path in P ______**

*AND*

**The Number of Control Path Possible in P ______**

Isn't it both represent different meaning?

0

@Mr_22B Now as P is not given in questions so we can assume it is POSSIBLE paths only. Had P be given in questions then it would be the other way

+20 votes

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.

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.

+17 votes

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

+4

i have one doubt..if is dreived only fro stmt..and it is not nested..how it can be one after other? how 1024..why not 20

+8

yes, it should be 20 ;as non-terminal stmnt is independent ...can't be nested ....

it occurs only like this (for 2 if terminals)

**if e1 else e2 else e3**

next as

**if e4 else e5 else e6**

**So, control paths will be e1-> e2,e1-> e3,e4-> e5,e4-> e6 (only four control paths for 2 if statements)**

**Correct me if I am Wrong!**

+17 votes

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.

+8 votes

people considering 2.2....=2^{10 } 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

+3

but since 10 if else statements are written one after other than also for every statement you have 2 choices right?

say you choose path 1 from 1st if then path 1 from 2nd if(case 1)

path 1 from 1st if then path 2 from 2nd if(case 2)

path 2 from 1st if then path 1 from 2nd if(case 3)

path 2 from 1st if then path 2 from 2nd if(case 4)

similarly you have 2*2*2*2.......(10 times) no of choices...what nesting has to do here its like you have 10 boxes in sequence and each has 2 different ball you have to tell number of sequence of choosing them serially right?

say you choose path 1 from 1st if then path 1 from 2nd if(case 1)

path 1 from 1st if then path 2 from 2nd if(case 2)

path 2 from 1st if then path 1 from 2nd if(case 3)

path 2 from 1st if then path 2 from 2nd if(case 4)

similarly you have 2*2*2*2.......(10 times) no of choices...what nesting has to do here its like you have 10 boxes in sequence and each has 2 different ball you have to tell number of sequence of choosing them serially right?

0

no if i select path 1 from 1st thats it.based on that i can not selet any path from2..1 and 2 is completely different.. here we have

2 choice for 1 if

2 choice for 2 if

2 choice for 3rd if

---------------

2 choice for 10th if

so 10.2 hoice for 10 tota if

2 choice for 1 if

2 choice for 2 if

2 choice for 3rd if

---------------

2 choice for 10th if

so 10.2 hoice for 10 tota if

0

but it ask number of control flow paths...thats how we do it i think in Software Engineering subject for making control flow graph..nd obviously its a program of 10 statements dependent or not does not matter..what matters is from beginning to end how may paths you have

0

i am also saying the same ..here sum rule of counting applies ..as they are independent in the grammar

0

so you are saying if there are 10 statements one after other each having 2 paths if asked total possible ways to move from begining to end is 20?

+5

sum rule is applied if you have to choose either statement one or 2 or....10...even if program need to check 2 statements product rule comes into picture....and if program checks one if statement and executes it then does the program stops or checks further?? here you have to go through every if till end

0

yes it may be the case.. if we selct path 2 suppose in my diagram..that is an end ..no way to go 3 or 4 from there

0

2 if-else statements will obviously be independent if 2nd is not using data of first...write a program in C and write 10 if else statement one after other...write printf("A"); in each....you will find 10 A's printed at end not 1

0

@Uddipto in your example you are doing nesting rt?

And a path differs even if one edge is different.

And a path differs even if one edge is different.

0

i am doing nesting of stmt ..not nesting of expr,on which solely if depends....so @Arjun sir you say it is 1024?

0

understand one thing.in ,my diagram..if i get into path 2... there is no way i can go to path 3..coz that is completely different if

0

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

0 votes

The first thing we need to know is given program(if statements) executes sequentially or in any order, so the answer is the program has been already written & given to us and now we can not decide which "if" statement will execute in which order, so it executes sequentially.

Now 1st "if" statement has 2 control flow paths, either it can direct its path to "then" statement or "else" statement. Similarly 2nd "if" statement has to 2 control flow paths. Now if we look closely, using these 2 "if" statement we can have 4 control flow paths.

**1) 1st "if" -> 1st "then" -> 2nd "if" -> 2nd "then"
2) 1st "if" -> 1st "then" -> 2nd "if" -> 2nd "else"
3) 1st "if" -> 1st "else" -> 2nd "if" -> 2nd "then"
4) 1st "if" -> 1st "else" -> 2nd "if" -> 2nd "else"**

Similarly for 10 "if" statements we can have 2^10=1024 control flow paths.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,389 answers

198,585 comments

105,434 users