1
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
Consider this C code to swap two integers and these five statements:
void swap(int *px, int *py) 
{ 
    *px = *px - *py; 
    *py = *px + *py; 
    *px = *py - *px; 
}
S1: will generate a compilation error

S2: may generate a segmentation fault at runtime depending on the arguments passed

S3: correctly implements the swap procedure for all input pointers referring to integers stored in memory locations accessible to the process

S4: implements the swap procedure correctly for some but not all valid input pointers

S5: may add or subtract integers and pointers.
A
S1
B
S2 and S3
C
S2 and S4
D
S2 and S5
2
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$$ s in $$s$$ and $${n_1}\left( s \right)$$ the number of $$1'$$s in $$s.$$ Which one of the following languages is not regular?
A
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {{n_0}\left( s \right)\,\,} \right.} \right.$$ is a $$3$$-digit prime$$\left. \, \right\}$$
B
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {\,\,} \right.} \right.$$ for every prefix $$s'$$ of $$s.$$ $$\,\left| {{n_0}\left( {{s^,}} \right) - {n_1}\left( {{s^,}} \right)\left| { \le \left. 2 \right\}} \right.} \right.$$
C
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^*}\left\| {{n_0}\left( s \right) - {n_1}\left( s \right)\left| { \le \left. 4 \right\}} \right.} \right.} \right.$$
D
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }} \right.\left| {{n_0}\left( s \right)} \right.$$ mod $$7 = {n_1}\left( s \right)$$ mod $$5 = \left. 0 \right\}$$
3
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enumerable, but not recursive, language. Which one of the following statement is false?
A
$${L_1} \cap {L_2}$$ is deterministic $$CFL$$
B
$${L_3} \cap {L_1}$$ is recursive
C
$${L_1} \cup {L_2}$$ is context-free
D
$${L_1} \cap {L_2} \cap {L_3}$$ is recursively enumerable
4
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$
Let $$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {\,d\left( s \right)\,} \right.} \right.$$ mod $$5=2$$ and $$d(s)$$ mod $$\left. {7 \ne 4} \right\}$$

Which of the following statement is true?

A
$$L$$ is recursively enumerable, but not recursive
B
$$L$$ is recursive, but not context-free
C
$$L$$ is context-free, but not regular
D
$$L$$ is regular
EXAM MAP