1
GATE CSE 2024 Set 1
MCQ (More than One Correct Answer)
+1
-0

Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

A

$L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \emptyset$

B

$L_1 \cup L_3$ is not regular

C

$\overline{L_3}$ is not regular

D

$L_1 \cup \overline{L_2}$ is regular

2
GATE CSE 2024 Set 1
MCQ (More than One Correct Answer)
+2
-0

Consider the 5-state DFA $M$ accepting the language $L(M) \subseteq (0+1)^*$ shown below. For any string $w \in (0+1)^*$ let $n_0(w)$ be the number of 0's in $w$ and $n_1(w)$ be the number of 1's in $w$.

GATE CSE 2024 Set 1 Theory of Computation - Finite Automata and Regular Language Question 12 English

Which of the following statements is/are FALSE?

A

States 2 and 4 are distinguishable in $M$

B

States 3 and 4 are distinguishable in $M$

C

States 2 and 5 are distinguishable in $M$

D

Any string $w$ with $n_0(w) = n_1(w)$ is in $L(M)$

3
GATE CSE 2024 Set 1
Numerical
+2
-0

Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = { a, b, c } and V containing 10 variable symbols including the start symbol S. The string w = a30b30c30 is derivable from S. The number of steps (application of rules) in the derivation S ⟹ w is _______

Your input ____
4
GATE CSE 2024 Set 1
Numerical
+2
-0

Consider the following two regular expressions over the alphabet {0,1} :

$$r = 0^* + 1^*$$

$$s = 01^* + 10^*$$

The total number of strings of length less than or equal to 5, which are neither in r nor in s, is ________

Your input ____
EXAM MAP