2022 question paper

Formal Language & Automata Theory

27 questions

Q1a. The language \{ a^m b^n c^{m+n} / m, n \ge 1 \} is (i) regular (ii) context-free but not regular (iii) Context-sensitive but not context free (iv) type-0 but not context sensitive20222m
Module 2: Context-free languages and pushdown automata
The language $\{ a^m b^n c^{m+n} / m, n \ge 1 \}$ is
(i) regular
(ii) context-free but not regular
(iii) Context-sensitive but not context free
(iv) type-0 but not context sensitive

View this question on its own page →
Search Google Ask AI
Q1b. Which of the following pairs have DIFFERENT expressive powers? (i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA) (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA) (iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine (iv) Single-tape Turing machine and multi-tape Turing machine20222m
Module 2: Context-free languages and pushdown automata
Which of the following pairs have DIFFERENT expressive powers?
(i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)
(ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
(iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine
(iv) Single-tape Turing machine and multi-tape Turing machine

View this question on its own page →
Search Google Ask AI
Q1c. The logic of pumping lemma is a good example of (i) pigeon-hole principle (ii) divide-and-conquer technique (iii) recursion (iv) iteration20222m
Module 1: Introduction, Regular languages and finite automata
The logic of pumping lemma is a good example of
(i) pigeon-hole principle
(ii) divide-and-conquer technique
(iii) recursion
(iv) iteration

View this question on its own page →
Search Google Ask AI
Q1d. If L1 and L2 are context free languages, L1 - L2 is ___________ context-free. (i) always (ii) sometimes (iii) never (iv) None of these20222m
Module 2: Context-free languages and pushdown automata
If $L1$ and $L2$ are context free languages, $L1 - L2$ is ___________ context-free.
(i) always
(ii) sometimes
(iii) never
(iv) None of these

View this question on its own page →
Search Google Ask AI
Q1e. ___________ is the acyclic graphical representation of a grammar (i) Binary tree (ii) Octtree (iii) Parse tree (iv) None of the above20222m
Module 2: Context-free languages and pushdown automata
___________ is the acyclic graphical representation of a grammar
(i) Binary tree
(ii) Octtree
(iii) Parse tree
(iv) None of the above

View this question on its own page →
Search Google Ask AI
Q1f. Which of the following pairs of regular expressions are equivalent? (i) x^* and x^*x (ii) 1(01)^* and (10)^*1 (iii) x(xx)^* and (xx)^*x (iv) All of the above20222m
Module 1: Introduction, Regular languages and finite automata
Which of the following pairs of regular expressions are equivalent?
(i) $x^*$ and $x^*x$
(ii) $1(01)^*$ and $(10)^*1$
(iii) $x(xx)^*$ and $(xx)^*x$
(iv) All of the above

View this question on its own page →
Search Google Ask AI
Q1g. The maximum number of states of a DFA converted from an NFA with n states is (i) n (ii) n^2 (iii) 2^n (iv) None of these20222m
Module 1: Introduction, Regular languages and finite automata
The maximum number of states of a DFA converted from an NFA with $n$ states is
(i) $n$
(ii) $n^2$
(iii) $2^n$
(iv) None of these

View this question on its own page →
Search Google Ask AI
Q1h. Definition of a language L with alphabet \{a\} is given as L= \{a^{nk} / k > 0, \text{ and } n \text{ is a positive integer constant}\}. What is the minimum number of states needed in a DFA to recognize L? (i) k + 1 (ii) n + 1 (iii) 2n + 1 (iv) 2k + 120222m
Module 1: Introduction, Regular languages and finite automata
Definition of a language $L$ with alphabet $\{a\}$ is given as $L= \{a^{nk} / k > 0, \text{ and } n \text{ is a positive integer constant}\}$ . What is the minimum number of states needed in a DFA to recognize L?
(i) $k + 1$
(ii) $n + 1$
(iii) $2n + 1$
(iv) $2k + 1$

View this question on its own page →
Search Google Ask AI
Q1i. A ___________ is context free grammar with atmost one non-terminal in the right handside of the production. (i) linear grammar (ii) linear bounded grammar (iii) regular grammar (iv) None of the above20222m
Module 2: Context-free languages and pushdown automata
A ___________ is context free grammar with atmost one non-terminal in the right handside of the production.
(i) linear grammar
(ii) linear bounded grammar
(iii) regular grammar
(iv) None of the above

View this question on its own page →
Search Google Ask AI
Q1j. Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true? (i) m \le 2^n (ii) n \le m (iii) M has one accept state (iv) m = 2^n20222m
Module 1: Introduction, Regular languages and finite automata
Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with $m$ states recognizing the same language. Which of the following is necessarily true?
(i) $m \le 2^n$
(ii) $n \le m$
(iii) $M$ has one accept state
(iv) $m = 2^n$

View this question on its own page →
Search Google Ask AI
Q2a. Tabulate Chomsky hierarchy of grammars with an example for each.20227m
Module 1: Introduction, Regular languages and finite automata
Tabulate Chomsky hierarchy of grammars with an example for each.

View this question on its own page →
Search Google Ask AI
Q2b. Construct the regular grammar accepting the following language: L = \{ w \in \{a, b\}^* / w \text{ is a string over } \{a, b\} \text{ such that the number of b's is } 3 \pmod 4 \}20227m
Module 1: Introduction, Regular languages and finite automata
Construct the regular grammar accepting the following language:
$L = \{ w \in \{a, b\}^* / w \text{ is a string over } \{a, b\} \text{ such that the number of b's is } 3 \pmod 4 \}$

View this question on its own page →
Search Google Ask AI
Q3a. Minimize the DFA shown in the following transition diagram: ![DFA Diagram](https://res.cloudinary.com/djkpavwmp/image/upload/v1772538790/portfolio_assets/n7vgbity0wgvcff7jesp.png)20227m
Module 1: Introduction, Regular languages and finite automata
Minimize the DFA shown in the following transition diagram:

View this question on its own page →
Search Google Ask AI
Q3b. Define recursively enumerable languages. Let L_1 be recursive and L_2 recursively enumerable. Show that L_2 - L_1 is necessarily recursively enumerable.20227m
Module 4: Turing machines
Define recursively enumerable languages. Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2 - L_1$ is necessarily recursively enumerable.

View this question on its own page →
Search Google Ask AI
Q4. Begin with the grammar: S \to ASB / \epsilon A \to aAS / a B \to SbS / A / bb (i) Eliminate \epsilon-productions. (ii) Eliminate unit productions in the resulting grammar. (iii) Eliminate any useless symbol in the resulting grammar. (iv) Put the resulting grammar into CNF.202214m
Module 2: Context-free languages and pushdown automata
Begin with the grammar:
$S \to ASB / \epsilon$
$A \to aAS / a$
$B \to SbS / A / bb$

(i) Eliminate $\epsilon$ -productions.
(ii) Eliminate unit productions in the resulting grammar.
(iii) Eliminate any useless symbol in the resulting grammar.
(iv) Put the resulting grammar into CNF.

View this question on its own page →
Search Google Ask AI
Q5a. Design a pushdown automata to accept the following language by empty stack: \{ 0^n 1^n / n \ge 1 \}.20227m
Module 2: Context-free languages and pushdown automata
Design a pushdown automata to accept the following language by empty stack: $\{ 0^n 1^n / n \ge 1 \}$ .

View this question on its own page →
Search Google Ask AI
Q5b. Define deterministic pushdown automata. Explain with an example.20227m
Module 2: Context-free languages and pushdown automata
Define deterministic pushdown automata. Explain with an example.

View this question on its own page →
Search Google Ask AI
Q6a. Prove using pumping lemma for regular languages that the language \{ 0^n / n \text{ is a perfect square} \} is not regular.20227m
Module 1: Introduction, Regular languages and finite automata
Prove using pumping lemma for regular languages that the language $\{ 0^n / n \text{ is a perfect square} \}$ is not regular.

View this question on its own page →
Search Google Ask AI
Q6b. Convert the following DFA to regular expression using the state elimination technique. | State/input | 0 | 1 | |---|---|---| | \to *p | s | p | | q | p | s | | r | r | q | | s | q | r |20227m
Module 1: Introduction, Regular languages and finite automata
Convert the following DFA to regular expression using the state elimination technique.

State/input 0 1

$\to *p$ s p

q p s

r r q

s q r

View this question on its own page →
Search Google Ask AI
Q7a. Convert the following NFA to DFA and informally describe the language it accepts. | State/input | 0 | 1 | |---|---|---| | \to p | {p, q} | {p} | | q | {r, s} | {t} | | r | {p, r} | {t} | | *s | \emptyset | \emptyset | | *t | \emptyset | \emptyset |20227m
Module 1: Introduction, Regular languages and finite automata
Convert the following NFA to DFA and informally describe the language it accepts.

State/input 0 1

$\to p$ {p, q} {p}

q {r, s} {t}

r {p, r} {t}

*s $\emptyset$ $\emptyset$

*t $\emptyset$ $\emptyset$

View this question on its own page →
Search Google Ask AI
Q7b. When a CFG is called ambiguous? Show that S \to as / aSbS / \epsilon is ambiguous.20227m
Module 2: Context-free languages and pushdown automata
When a CFG is called ambiguous? Show that $S \to as / aSbS / \epsilon$ is ambiguous.

View this question on its own page →
Search Google Ask AI
Q8a. Define Turing machine. Design a Turing machine M to recognize the language \{ 1^n 2^n 3^n / n \ge 1 \}.20227m
Module 4: Turing machines
Define Turing machine. Design a Turing machine $M$ to recognize the language $\{ 1^n 2^n 3^n / n \ge 1 \}$ .

View this question on its own page →
Search Google Ask AI
Q8b. Construct DFA equivalent to the regular expression: (0+1)^* (00+11) (0+1)^*20227m
Module 1: Introduction, Regular languages and finite automata
Construct DFA equivalent to the regular expression: $(0+1)^* (00+11) (0+1)^*$

View this question on its own page →
Search Google Ask AI
Q9i. Write short notes on: Pumping lemma for CFL20227m
Module 2: Context-free languages and pushdown automata
Write short notes on: Pumping lemma for CFL

View this question on its own page →
Search Google Ask AI
Q9ii. Write short notes on: GNF20227m
Module 2: Context-free languages and pushdown automata
Write short notes on: GNF

View this question on its own page →
Search Google Ask AI
Q9iii. Write short notes on: Multistack Turing Machine20227m
Module 4: Turing machines
Write short notes on: Multistack Turing Machine

View this question on its own page →
Search Google Ask AI
Q9iv. Write short notes on: NP-hard problem20227m
Module 5: Undecidability
Write short notes on: NP-hard problem

View this question on its own page →
Search Google Ask AI

State/input	0	1
$\to *p$	s	p
q	p	s
r	r	q
s	q	r

State/input	0	1
$\to p$	{p, q}	{p}
q	{r, s}	{t}
r	{p, r}	{t}
*s	$\emptyset$	$\emptyset$
*t	$\emptyset$	$\emptyset$

Previous year2021 Next year2025