FORMAL LANGUAGE & AUTOMATA THEORY

The minimum number of states required to recognize an octal number divisible by 3 is:

(i) 1
(ii) 3
(iii) 5
(iv) 7

Which of the following is a regular language?

(i) Strings whose length is a sequence of prime numbers
(ii) Palindrome strings
(iii) Strings containing substring $ww^r$
(iv) Strings with even number of $0$’s

Regular languages belong to which type in the Chomsky hierarchy?

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

For a given Moore machine, given input = 101010, the output would be of length:

(i) |Input| + 1
(ii) |Input|
(iii) |Input| − 1
(iv) Cannot be predicted

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$

A minimum state deterministic FA accepting the language:

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

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

Which of the following languages is NOT regular?

(i) {$a^n b^n | n \ge 0$}
(ii) {$a, b$}*
(iii) Finite languages
(iv) Languages accepted by DFA

NFA has 'non-deterministic' in its name because:

(i) The result is undetermined
(ii) The choice of path is nondeterministic
(iii) The next state is nondeterministic
(iv) All of the mentioned

The total number of states and transitions required to form a Moore machine that produces residue mod 3 are:

(i) 3 and 6
(ii) 3 and 5
(iii) 2 and 4
(iv) 2 and 5

Which of the following is NOT a component of a finite automaton?

(i) States
(ii) Input alphabet
(iii) Transition function
(iv) Output tape

Which of the following is a correct statement?

(i) Moore machine has no accepting states.
(ii) Mealy machine has accepting states.
(iii) We can convert Mealy to Moore but not vice versa.
(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 the above

A DFA can have:

(i) Multiple start states
(ii) Multiple accepting states
(iii) Transitions on $\varepsilon$
(iv) None of the above

The string $1101$ does not belong to the set represented by:

(i) $1^* 0^* (0+1)$
(ii) $1(0+1)^*101$
(iii) $(1(0)^*(0+1)^*(0+1))^*$
(iv) $\{00 + (11)^*0\}^*$

The minimum number of transitions to reach the final state as per the regular expression:

$$\{a, b\}^* baaa$$

is:

(i) 4
(ii) 5
(iii) 6
(iv) 3

Which of the following is a type of grammar in the Chomsky hierarchy?

(i) Regular
(ii) Context-Free
(iii) Context-Sensitive
(iv) All of the above

Let $w = xyz$, $y$ is the middle portion and $|y| > 0$. Repeating $y$ zero or more times before checking membership in $L$ is known as:

(i) Generating
(ii) Pumping
(iii) Producing
(iv) None of the above

For an NFA with $n$ states, the minimized DFA has:

(i) $m \le 2^n$
(ii) $n \le m$
(iii) one accept state
(iv) $m = 2^n$

If $\Sigma = \{a, b\}$, then $\Sigma^*$ contains

(i) Only finite strings
(ii) Only infinite strings
(iii) All finite strings over $\Sigma$ including $\epsilon$
(iv) Only strings of equal length

The $\epsilon$-closure of a state is

(i) The set of states reachable using $\epsilon$ only
(ii) The set of unreachable states
(iii) The set of final states
(iv) The dead states

Which of these represents a regular language?

(i) $\{ a^n b^n \mid n \ge 0 \}$
(ii) Strings with equal number of $a$’s and $b$’s
(iii) $\{ a^n \mid n \text{ is prime} \}$
(iv) $\{ w \mid w \text{ starts with 'a' and ends with 'b'} \}$

A minimum state DFA for the language:

$$L = \{ w \in \{0,1\}^* : \#0(w) \equiv 0 \mod 3,\; \#1(w) \equiv 0 \mod 5 \}$$

has:

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

If $P$ and $Q$ are regular expressions ($P$ is not null), then $R = Q + RP$ has the unique solution:

(i) $R = QP$
(ii) $R = PQ^*$
(iii) $R = QP^*$
(iv) $R = QP^*$

The construction time for DFA from NFA with $m$ nodes is:

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

What is Automata? Explain classification of Automata.

Discuss the Chomsky hierarchy of grammars with suitable examples.

Design a DFA for strings over $\{a, b\}$ containing at least three occurrences of bbb (overlapping allowed). Example: bbbbbb is accepted.

Tabulate the Chomsky hierarchy of grammars with an example for each.

Explain the Chomsky hierarchy of languages with examples.

Tabulate the Chomsky hierarchy of grammars with an example of each.

Let $L \subseteq \{0,1,2\}^*$ be strings without consecutive identical symbols (no $00$, no $11$, no $22$). Design a DFA for $L$.

Design a finite-state machine (FSM) for a parity checker.

Construct DFA for all strings over $\{0,1\}$ interpreted as binary numbers divisible by $4$.

Construct an NFA accepting strings over $\{0,1,2\}$ beginning with 0, followed by an odd number of 1s, ending with any number of 2s.

Construct DFA that accepts strings over $\Sigma = \{a,b\}$ which start with $aba$.

Given the regular expression:
$(0+1)^*01(0+1)$

Describe the language generated, and construct an equivalent DFA.

Prove that $L = \{ a^i b^i \mid i \ge 0 \}$ is not regular using the pumping lemma.

Design Mealy and Moore machines to detect the sequence 1010 (overlapping allowed). Then convert the Moore machine into a Mealy machine and prove equivalence.

Given a DFA D over the alphabet {a, b}, perform DFA minimization and draw the equivalent minimal DFA accepting the same language.

Convert the following NFA to DFA.

Obtain the regular expression for the given DFA.

Design a DFA for the regular expression:

$$1^*(10)^*$$

Use the pumping lemma to prove that the language $L = \{a^n b^n : n \ge 1\}$ is not regular.

Prove that if $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is regular.

Give examples of $L_1$ and $L_2$ such that:

(i) $L_1$ is regular, $L_2$ is not regular, and $L_1 - L_2$ is regular.
(ii) $L_1$ and $L_2$ are not regular but $L_1 \cup L_2$ is regular.

Show that the language of palindromes over $\{a, b\}$ is not regular.

Construct an NFA that accepts all strings over the alphabet {0, 1, 2} that begin with one or more 0s, followed by an odd number of 1s, and end with any number of 2s.

Given the $\varepsilon$-NFA, compute $\varepsilon$-closures and convert to DFA.

State	$\varepsilon$-transition	a-transition	b-transition
→	{r}	{q}	{p,r}
q	∅	{p}	∅
r	{p,q}	{r}	{p}

Show that the language:

$$L = \{ a^{n!} : n \ge 0 \}$$

is not regular or not context-free.

Construct NFA for the regular expression:

$$(0+1)^*00(0+1)^*$$