1
GATE CSE 1992
+2
-0.6
If $$G$$ is a context-free grammar and $$w$$ is a string of length $$n$$ in $$L(G),$$ how long is a derivation of $$w$$ in $$G,$$ if $$G$$ is Chomsky normal form?
A
$$2n$$
B
$$2n+1$$
C
$$2n-1$$
D
$$n$$
2
GATE CSE 1991
+2
-0.6
Let $$r = 1\,{\left( {1 + 0} \right)^ * },s = {11^ * }\,0$$ and $$\,t = {1^ * }\,0$$ be three regular expressions. Which one of the following is true?
A
$$L\left( s \right) \subseteq L\left( r \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( t \right)\,\,$$
B
$$L\left( r \right) \subseteq L\left( s \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( t \right)\,\,$$
C
$$L\left( s \right) \subseteq L\left( t \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( r \right)\,\,$$
D
$$L\left( t \right) \subseteq L\left( s \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( r \right)\,\,$$
3
GATE CSE 1990
+2
-0.6
Let $${R_1}$$ and $${R_2}$$ be regular sets defined over the alphabet $$\sum \,$$ then:
A
$${R_1} \cap R{}_2$$ is not regular.
B
$${R_1} \cup R{}_2$$ is regular.
C
$$\sum {^{^ * }}$$ $$-$$ $${R_1}$$ is regular.
D
$${R_1}{}^ *$$ is not regular.
4
GATE CSE 1989
Subjective
+2
-0
How many substrings (of all lengths inclusive ) can be formed from a character string of length $$n$$? Assume all characters to be distinct. Prove your answer.
GATE CSE Subjects
EXAM MAP
Medical
NEET