FORMAL LANGUAGES AND AUTOMATA THEORY - B.Tech 5th Semester Exam., 2021

Which of the following statements is/are False?

1. A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. B. Turing recognizable languages are closed under union and complementation.
3. C. Turing decidable languages are closed under intersection and complementation.
4. D. Turing recognizable languages are closed under union and intersection.
5. (i) A and D only (ii) A and C only (iii) B only (iv) C only

Enumerator is a Turing machine with

1. an output printer
2. 5 input tapes
3. a stack
4. None of the above

The language \( \{a^m b^n c^{m+n} \mid m, n \ge 1\} \) is

1. regular
2. context-free but not regular
3. context-sensitive but not context-free
4. type-0 but not context-sensitive

The maximum number of states of a DFA converted from an NFA with \( n \) states is

1. \( n \)
2. \( n^2 \)
3. \( 2^n \)
4. None of the above

If \( L_1 \) and \( L_2 \) are context-free languages, \( L_1 - L_2 \) is

1. always context-free.
2. sometimes context-free.
3. never context-free.
4. None of the above

Which of the following does not have left recursions?

1. Chomsky normal form
2. Greibach normal form
3. Backus-Naur form
4. All of the above

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?

1. \( m \le 2^n \)
2. \( n \le m \)
3. M has one accept state
4. \( m = 2^n \)

_____ is the acyclic graphical representation of a grammar.

1. Binary tree
2. Octtree
3. Parse tree
4. None of the above

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

1. 15 states
2. 11 states
3. 10 states
4. 9 states

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

1. \( O(m^2) \)
2. \( O(2^m) \)
3. \( O(m) \)
4. \( O(\log m) \)

Tabulate Chomsky hierarchy of grammar with an example for each.

Design a finite state machine abstract model for Parity checker.

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.

Construct a push-down automata that accepts the following language: \( L = \{uawb : u \text{ and } w \in (a,b)^* \text{ and } |u| = |w|\} \)

Design a Turing machine (TM) to compute \( n \mod 2 \).

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

Consider the grammar: \( S \rightarrow AB \mid BC \), \( A \rightarrow BA \mid a \), \( B \rightarrow CC \mid b \), \( C \rightarrow AB \mid a \). Use the CYK algorithm to determine whether the given string "baaba" is in \( L(G) \) or not.

Suppose L is context free and R is regular, justify your answer with the help of example:
(i) Is \( L - R \) necessarily context free?
(ii) Is \( R - L \) necessarily context free?

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

Let G be a context-free grammar in Chomsky normal form that contains \( b \) variable. Show that if G generates some string using a derivation with at least \( 2^b \) steps, then \( L(G) \) is infinite.

State and prove pumping lemma for regular sets.

Show given grammar over alphabet {a, b}, verify whether it is ambiguous or unambiguous : \( S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon \)

Show that the sum function \( f(x, y) = x + y \) is primitive recursive.

Construct a PDA that accepts the language \( L = \{a^{2n}bc \mid n \ge 0\} \) by final state and empty stack.

• Post-correspondence problem
• Chomsky normal form
• Multistack Turing machine
• Pumping lemma for CFL