Consider the recursive functions represented by the following code segment:

int bar(int n){

    if (n == 1) return 0;

    else return 1 + bar(n/2);

}

int foo(int n){

    if (n == 1) return 1;

    else return 1 + foo(bar(n));

}

The smallest positive integer n for which foo(n) returns 5 is $\_\_\_\_$ . (answer in integer)

Note: Ignore syntax errors (if any) in the function.

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols.

$$ S \rightarrow a S b S|b S| \in $$

Which of the following statements is/are true?

Let $M$ be a non-deterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ?

Let $L_1$ and $L_2$ be two languages over a finite alphabet, such that $L_1 \cap L_2$ and $L_2$ are regular languages.

Which of the following statements is/are always true?