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

2019•Semester 2•Civil-CA•End Semester
Bihar Engineering University, Patna
B.Tech 6th Semester Exam., 2019

FORMAL LANGUAGES AND AUTOMATA THEORY

Time: 03 HoursCode: 051611Full Marks: 70

Instructions:

  1. The marks are indicated in the right-hand margin.
  2. There are NINE questions in this paper.
  3. Attempt FIVE questions in all.
  4. Question No. 1 is compulsory.
Q.1 Choose the correct answer/Fill in the blank of any seven of the following:[14]

  1. The word 'formal' in formal languages means

    1. they are unnecessary, in reality
    2. the symbols used have well-defined meaning
    3. only the form of the string of symbols is significant
    4. None of the above

  2. Which of the following statements is true?

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

  3. Which of the following pairs of regular expressions are equivalent?

    1. \( x^* \) and \( x^*x \)
    2. \( 1(01)^* \) and \( (10)^*1 \)
    3. \( x(xx)^* \) and \( (xx)^*x \)
    4. All of the above

  4. Which of the following pairs have DIFFERENT expressive powers?

    1. Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)
    2. Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
    3. Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine
    4. Single-tape Turing machine and multi-tape Turing machine

  5. Definition of a language L with alphabet {a} is given as \( L = \{a^{nk} \mid k > 0 \text{ and n is a positive integer constant}\} \). What is the minimum number of states needed in a DFA to recognize L?

    1. \( k + 1 \)
    2. \( n + 1 \)
    3. \( 2n + 1 \)
    4. \( 2k + 1 \)

  6. Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP complete (NPC)?

    Question Diagram
    1. (A) P and NP are disjoint
    2. (B) P and NP overlap, with NPC in intersection
    3. (C) P = NP = NPC
    4. (D) P != NP, NPC inside NP

  7. Let L1 be a recursive language. Let L2 and L3 be languages that are not recursively enumerable but recursive. Which of the following statements is not necessarily true?

    1. L2-L1 is recursively enumerable.
    2. L1-L3 is recursively enumerable.
    3. L2 ∩ L1 is recursively enumerable.
    4. L2 ∪ L1 is recursively enumerable.

  8. A PDM behaves like an FSM when the number of auxiliary memory it has, is

    1. 0
    2. 1
    3. 2
    4. None of the above

  9. Define Turing machine in brief.

  10. A finite automaton with _____ is equivalent to push-down automata.

Q.2 Solve this question :[14]

  1. Consider the set of strings on {0, 1} defined by the requirements below. For each, construct an accepting dfa:
    (i) Every 00 is followed immediately by a 1. For example, the strings 101, 0010, 001001 are in the language, but 0001 and 00100 are not.
    (ii) All strings containing 00 but not 000.
    (iii) The leftmost symbol differs from the rightmost one.
    (iv) Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

Q.3 Solve both questions :[14]

  1. Construct the regular grammar accepting the following language: \( L = w \in \{a, b\}^* \mid w \text{ is a string over } \{a, b\} \) \( \text{ such that the number of b's is } 3 \mod 4 \)

  2. Let \( G = (V, T, S, P) \) be a right-linear grammar. Prove that the language generated using the grammar G is a regular.

Q.4 Solve both questions :[14]

  1. Construct a Moore machine equivalent to the Mealy machine M defined by the following Table 1 state transitions:

    Present State a = 0 a = 1
    Next State Output Next State Output
    \( q_1 \) \( q_1 \) 1 \( q_2 \) 0
    \( q_2 \) \( q_4 \) 1 \( q_4 \) 1
    \( q_3 \) \( q_2 \) 1 \( q_3 \) 1
    \( q_4 \) \( q_3 \) 0 \( q_1 \) 1

  2. Prove the following equation : \( (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) \) = \( 0^*1(0+10^*1)^* \)

Q.5 Solve this question :[14]

  1. Using the pumping lemma theorem, show that the following sets are not regular:

    \( L = \{a^n b^l a^k : k \ge n+l\} \)

    \( L = \{w : n_a(w) = n_b(w)\} \)

    \( L = \{ww w^R : w \in \{a,b\}^*\} \)

Q.6 Solve both questions :[14]

  1. Convert the grammar into Chomsky normal form: \( S \rightarrow aB \mid AB \), \( A \rightarrow aab \mid \lambda \), \( B \rightarrow bbA \)

  2. Show that the family of unambiguous context-free languages is not closed under union.

Q.7 Solve this question :[14]

  1. Construct an npda corresponding to the grammar: \( S \rightarrow aABB \mid aAA \), \( A \rightarrow aBB \mid a \), \( B \rightarrow bBB \mid A \)

Q.8 Solve this question :[14]

  1. Construct Turing machines that will accept the following languages on {a, b}:

    \( L = \{w : n_a(w) = n_b(w)\} \)

    \( L = \{wcw : w \in \{a,b\}^*\} \)

Q.9 Solve both questions :[14]

  1. Design a Turing machine with no more than three states that accepts the language \( L(a(a+b)^*) \). Assume that \( \Sigma = \{a, b\} \). Is it possible to do this with a two-state machine?

  2. Let G be an undirected graph. An Euler circuit of the graph is a simple cycle that includes all edges. The Euler Circuit Problem (EULER) is to decide if G has an Euler circuit. Show that EULER is not NP-complete.