1
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
Consider the following statements about the context-free grammar
$$G = \left\{ {S \to SS,\,S \to ab,\,S \to ba,\,S \to \varepsilon } \right\}$$
$$1.$$ $$G$$ is ambiguous
$$2.$$ $$G$$ produces all strings with equal number of $$a's$$ and $$b's$$
$$3.$$ $$G$$ can be accepted by a deterministic $$PDA$$.

Which combination below expresses all the true statements about $$G?$$

A
$$1$$ only
B
$$1$$ and $$3$$ only
C
$$2$$ and $$3$$ only
D
$$1, 2$$ and $$3$$
2
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
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
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12