# Theory of Computation

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

$L = \{w \in \{0, 1\}^* | w \text{ does not contain three or more consecutive 1's} \}.$
The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____.
 A 3 B 4 C 5 D 6
GATE CSE 2023      Finite Automata
Question 1 Explanation:
 Question 2
Consider the pushdown automaton (PDA) $P$ below, which runs on the input alphabet $\{a,b\}$, has stack alphabet $\{ \perp ,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 , $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 $\perp$ in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by $P$?
 A $\{ a^mb^n |1\leq m\text{ and }n \lt m \}$ B $\{ a^mb^n |0 \leq n \leq m \}$ C $\{ a^mb^n |0\leq m\text{ and } 0 \lt n \}$ D $\{ a^m |0\leq m \} \cup \{b^n|0 \leq n \}$
GATE CSE 2023      Push-down Automata
Question 2 Explanation:

 Question 3
Consider the context-free grammar $G$ below
$S\rightarrow aSb \;| \;X$
$X\rightarrow aX \;| \;Xb \;|\; a\;|\; b$
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 \text{ is }(a + b)^*$ B The language generated by $G \text{ is } a^*(a + b)b^*$ C The language generated by $G \text{ is }a^*b^*(a + b)$ D The language generated by $G$ is not a regular language
GATE CSE 2023      Context Free Grammar
Question 3 Explanation:
 Question 4
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.
GATE CSE 2023      Context Free Language
Question 4 Explanation:
 Question 5
Consider the following definition of a lexical token $id$ for an identifier in a programming language, using extended regular expressions:

$letter \rightarrow [A-Za-z]$
$digit \rightarrow [0-9]$
$id \rightarrow letter (letter\;| \;digit)^*$

Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

 A A B B C C D D
GATE CSE 2023      Regular Expression
Question 5 Explanation:

There are 5 questions to complete.

### 1 thought on “Theory of Computation”

1. Two options of Q15 are the same.