FORMAL LANGUAGES AND AUTOMATA THEORY - B.Tech 6th Semester Exam., 2018

Regular expressions are closed under

1. union
2. intersection
3. Kleene star
4. All of the above

Extended transition function is

1. \( Q \times \Sigma^* \rightarrow Q \)
2. \( Q \times \Sigma^* \rightarrow \Sigma \)
3. \( Q \times \Sigma \rightarrow Q \)
4. \( Q \times \Sigma \rightarrow \Sigma \)

From the options given below, the pair having different expressive powers is

1. deterministic pushdown automata (DPDA) and non-deterministic pushdown automata (NPDA)
2. deterministic finite automata (DFA) and non-deterministic finite automata (NFA)
3. single-tape turing machine and multi-tape turing machine
4. deterministic single-tape turing machine and non-deterministic single-tape turing machine

For the language \( \{a^p \mid p \text{ is a prime}\} \), the statement which holds true is

1. it is not regular but context-free
2. it is regular but not context-free
3. it is neither regular nor context-free, but accepted by a turing machine
4. it is not accepted by turing machine

Which one of the following statements is true?

1. The intersection of two context-free languages is context-free.
2. A context-free language can always be accepted by a deterministic push-down automaton.
3. The union of two context-free languages is context-free.
4. The complement of a context-free language is context-free.

A class of language that is closed under

1. union and complementation has to be closed under intersection
2. intersection and complement has to be closed under union
3. union and intersection has to be closed under complementation
4. Both (i) and (ii)

CFG can be recognized by

1. a push-down automaton
2. a 2-way linear bounded automaton
3. Both (i) and (ii)
4. None of the above

A given grammar is called ambiguous, if

1. two or more productions have the same non-terminal on the left-hand side
2. a derivation tree has more than one associated sentence
3. there is a sentence with more than one derivation tree corresponding to it
4. brackets are not present in the grammar

The output of the Mealy machine depends

1. only on present state
2. only on current input symbol
3. both on present state and current input symbol
4. None of the above

The logic of pumping lemma is a good example of

1. pigeon-hole principle
2. divide-and-conquer technique
3. recursion
4. iteration

For each of the following languages, construct a DFA that accepts the language. In all cases, the alphabet is {0, 1}:
(i) {w : the length of w is divisible by three}
(ii) {w : 110 is not a substring of w}
(iii) {w : w contains at least five 1's}
(iv) {w : w contains the substring 1011}
(v) {w : w contains at least two 1's and at most two 0's}

State and proof pumping lemma for regular languages.

Using pumping lemma, show that the language \( A = \{ww \mid w \in \{0, 1\}^*\} \) is not regular.

Let A be a non-empty regular language. Prove that there exists an NFA that accepts A and that has exactly one accept state.

Convert each of the following regular expressions to an NFA: (i) \( (0 \cup 1) 1^* 000 (0 \cup 1)^* \) (ii) \( (((10)^*(001) \cup 10))^* \) (iii) \( (baa + abb)^* \)

(a) Prove the following two properties: (i) Regular sets are closed over the intersection operation. (ii) Regular sets are closed over the union operation.
(b) Represent the language that contains strings over \( \Sigma = \{0, 1\} \) and has even number of 0's.
(c) Convert the following DFA to a regular expression:

(a) Construct context-free grammars that generate the following languages. In all cases \( \Sigma = \{a, b\} \): (i) \( a^*b \) (ii) \( (ab)^* \)
(b) Construct a CFG for the set of non-negative odd integers.

Let A and B be context-free languages over the same alphabet \( \Sigma \).
(i) Prove that the union \( A \cup B \) of A and B is also context-free.
(ii) Prove that the concatenation AB of A and B is also context-free.
(iii) Prove that the star \( A^* \) of A is also context-free.

Determine a CFG without unit production equivalent to the CFG given below: \( S \rightarrow a \mid Xb \mid aYa \mid b \mid aa \), \( X \rightarrow Y \), \( Y \rightarrow b \mid X \)

(a) Find the CNF (Chomsky Normal Form) for the following CFG: \( S \rightarrow ABA \), \( A \rightarrow aA \mid \epsilon \), \( B \rightarrow bB \mid \epsilon \)
(b) Eliminate null productions from the following CFG: \( S \rightarrow Xa \), \( X \rightarrow aX \mid bX \mid \epsilon \)
(c) Convert the following grammar to GNF: \( A_1 \rightarrow A_2 A_3 \), \( A_2 \rightarrow A_3 A_1 \mid b \), \( A_3 \rightarrow A_1 A_2 \mid a \)

Construct npda that accepts the following languages on \( \Sigma = \{a, b, c\} \):
(i) \( L = \{a^n b^{2n} : n \ge 0\} \)
(ii) \( L = \{wcw^R : w \in \{a,b\}^*\} \)
(iii) \( L = \{w : n_a(w) = 2n_b(w)\} \)

Design a PDA that accepts the language \( L = \{a^n b^m a^n : m, n > 0\} \)

(a) Design a Turing machine that recognizes strings containing equal number of 0's and 1's.
(b) Let \( L_1 \) be recursive and \( L_2 \) recursively enumerable. Show that \( L_2 - L_1 \) is necessarily recursively enumerable.
(c) Define P, NP, NPH and NPC problems with example.