Formal Language & Automata Theory

Which of the following is the smallest unit in the definition of a language?

(i) Grammar
(ii) Alphabet
(iii) String
(iv) Production

Consider the following finite state automaton:

The language accepted by this automaton is given by the regular expression
(i) $b^*ab^*ab^*ab$
(ii) $(a+b)^*$
(iii) $b^*a(a+b)^*$
(iv) $b^*ab^*ab$

Definition of a language $L$ with alphabet $\{a\}$ is given as

$$L = \{a^{nk} \mid 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) $2^{n + 1}$
(iv) $2^{k + 1}$

A language is a

(i) Set of alphabets
(ii) Set of strings over an alphabet
(iii) Set of grammars
(iv) Set of automata

A minimum state deterministic finite automaton accepting the language

$$L = \{w \mid w \in \{0, 1\}^*, \text{ number of 0's and 1's in } w \text{ are divisible by 3 and 5 respectively}\}$$

has
(i) 15 states
(ii) 11 states
(iii) 10 states
(iv) 9 states

The logic of pumping lemma is a good example of
(i) pigeon-hole principle
(ii) divide-and-conquer technique
(iii) recursion
(iv) iteration

Which grammar type is the most powerful?

(i) Type-0
(ii) Type-1
(iii) Type-2
(iv) Type-3

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 the above

Epsilon ($\varepsilon$) transitions are allowed in

(i) DFA only
(ii) Both DFA and NFA
(iii) NFA only
(iv) None

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

The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

(i) Finite state automata
(ii) Deterministic pushdown automata
(iii) Non-deterministic pushdown automata
(iv) Turing machine

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

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

Let $w$ be any string of length $n$ in $\{0, 1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in a non-deterministic FA that accepts $L$?

(i) $n - 1$
(ii) $n$
(iii) $n + 1$
(iv) $2n - 1$

Let $L = \{w \mid w \in \{0+1\}^*, w \text{ has even number of 1s}\}$. Which one of the regular expression below represents $L$?

(i) $(0^* 10^* 1)^*$
(ii) $0^*(10^* 10^*)^*$
(iii) $0^* (10^* 1^*)^* 0^*$
(iv) $0^* 1(10^* 1)^* 10^*$

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$

Consider the regular expression $(0+1)(0+1)\dots N \text{ times}$. The minimum state FA that recognizes the language represented by this regular expression contains

(i) $n$ states
(ii) $(n+1)$ states
(iii) $(n+2)$ states
(iv) None of the above

What is the minimum number of states in deterministic finite automata (DFA) for string starting with $ba^2$ and ending with $a$ over alphabet $\{a, b\}$?

(i) Ten
(ii) Nine
(iii) Eight
(iv) Six

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$

In Mealy machine, output is a function of

(i) present state only
(ii) next state only
(iii) present state and input
(iv) input only

A minimum state deterministic FA accepting the language

$$L = \{w \mid w \in \{0, 1\}^*\}$$

where number of 0's and 1's in $w$ are divisible by 3 and 5 respectively, has

(i) 15 states
(ii) 11 states
(iii) 10 states
(iv) 9 states

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 = 2n$

The construction time for DFA from an equivalent NFA ($m$ number of node) is

(i) $O(m^2)$
(ii) $O(2^m)$
(iii) $O(m)$
(iv) $O(\log m)$

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$

Design deterministic finite automata for the set of strings over the alphabet $\{a, b\}$ containing at least three occurrences of three consecutive $b$'s, overlapping permitted (e.g., the string $bbbbb$ should be accepted).

Tabulate Chomsky hierarchy of grammar with an example for each.

Tabulate Chomsky hierarchy of grammars with an example for each.

Define the terms: Alphabet, Language, Grammar, and Derivation. Explain the relationship between them with suitable examples.

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 \}$

Explain Chomsky Hierarchy of languages with examples of each type and their corresponding automata.

Let $\Sigma = \{0, 1\}$. Let $L$ be the language that consists of strings having either $01$ repeated one or more times or $010$ repeated one or more times. Is $L$ regular? Explain.

Construct a DFA which accepts the set of all binary strings that interpreted as binary representation of an unsigned decimal integer, is divisible by 5.

Design a finite state machine or abstract model for Parity checker.

Assume that a regular language $L$ is provided to you as a DFA $M(\{Q, \Sigma, \delta, q_0, F\})$. How would you check whether $L$ is infinite?

Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.

Minimize the DFA shown in the following transition diagram:

Explain the concept of a Finite Automaton. List and describe its main components. Also, differentiate between Deterministic Finite Automaton and Non-deterministic Finite Automaton with suitable examples.

Construct a DFA that accepts all strings over $\{0,1\}$ containing an even number of 0s and an odd number of 1s. Also, write its formal 5-tuple definition.

Construct a Moore machine which determines the residue mod 3 for each binary string treated as binary integer. And then convert into the corresponding Mealy machine.

Construct finite automaton corresponding to the regular expression:

$$(a+b)^* c d^* e$$

Convert the regular expression $(a + b)abb(a + b)$ into an equivalent DFA. Show all steps.

Design finite state machine or abstract model for binary adder.

Design a DFA corresponding to regular expression $1^*(10)^*$.

Using Pumping Lemma, prove that the language $L = \{0^{n}1^{n} \mid n \ge 0\}$ is not regular.

Show that $L = \text{palindrome over } \{a, b\}$ is not regular.

Show that the language $L = \{a^{n!} : n \ge 0\}$ is not regular or not context-free language.

Prove using pumping lemma for regular languages that the language $\{ 0^n / n \text{ is a perfect square} \}$ is not regular.

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

State and prove pumping lemma for regular sets.

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$