1
GATE CSE 2023
MCQ (More than One Correct Answer)
+1
-0.33

Which of the following statements is/are CORRECT?

A
The intersection of two regular languages is regular.
B
The intersection of two context-free languages is context-free.
C
The intersection of two recursive languages is recursive.
D
The intersection of two recursively enumerable languages is recursively enumerable.
2
GATE CSE 2023
MCQ (Single Correct Answer)
+2
-0.67

Consider the context-free grammar G below

$$\matrix{ S & \to & {aSb|X} \cr X & \to & {aX|Xb|a|b,} \cr } $$

where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S.

Which one of the following statements is CORRECT?

A
The language generated by G is $$(a+b)^*$$
B
The language generated by G is $$a^*(a+b)b^*$$
C
The language generated by G is $$a^*b^*(a+b)$$
D
The language generated by G is not a regular language
3
GATE CSE 2023
MCQ (Single Correct Answer)
+2
-0.67

Consider the pushdown automation (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {$$\bot$$, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/$$\gamma$$, where c is an input symbol or $$\in $$, X is a stack symbol, and $$\gamma$$ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string $$\gamma$$ on the stack, and go to state v. In the initial configuration, the stack has only the symbol $$\bot$$ in it. The PDA accepts by empty stack.

GATE CSE 2023 Theory of Computation - Push Down Automata and Context Free Language Question 4 English

Which one of the following options correctly describes the language accepted by P?

A
$$\{ {a^m}{b^n}|1 \le m\,\mathrm{and}\,n < m\} $$
B
$$\{ {a^m}{b^n}|0 \le n \le m\} $$
C
$$\{ {a^m}{b^n}|0 \le m\,\mathrm{and}\,0 \le n\} $$
D
$$\{ {a^m}|0 \le m\} \cup \{ {b^n}|0 \le n\} $$
4
GATE CSE 2023
Numerical
+2
-0.67

Consider the language L over the alphabet {0, 1}, given below:

$$L = \{ w \in {\{ 0,1\} ^ * }|w$$ does not contain three or more consecutive $$1's\} $$.

The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is ___________.

Your input ____
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12