GATE CSE 1994 | Finite Automata and Regular Language Question 93 | Theory of Computation

PREVIOUS NEXT

GATE CSE 1994

MCQ (Single Correct Answer)

-0.6

The number of sub-strings (of all lengths inclusive) that can be formed from a character string of length $$n$$ is

$$n$$

$${n^2}$$

$${{n\left( {n - 1} \right)} \over 2}$$

$${{n\left( {n + 1} \right)} \over 2}$$

GATE CSE 1992

MCQ (Single Correct Answer)

-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?

$$2n$$

$$2n+1$$

$$2n-1$$

$$n$$

GATE CSE 1992

MCQ (Single Correct Answer)

-0.6

Which of the following regular expression identities are true?

$$r\left( {^ * } \right) = r{}^ * $$

$$\left( {r{}^ * s{}^ * } \right){}^ * = \left( {r + s} \right){}^ * $$

$$\,\left( {r + s} \right){}^ * = r{}^ * + s{}^ * $$

$$r{}^ * s{}^ * = r{}^ * + s{}^ * $$

GATE CSE 1991

MCQ (Single Correct Answer)

-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?

$$L\left( s \right) \subseteq L\left( r \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( t \right)\,\,$$

$$L\left( r \right) \subseteq L\left( s \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( t \right)\,\,$$

$$L\left( s \right) \subseteq L\left( t \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( r \right)\,\,$$

$$L\left( t \right) \subseteq L\left( s \right)\,\,$$ and $$L\left( s \right) \subseteq L\left( r \right)\,\,$$

PREVIOUS NEXT